# Writing a code on flattening a family of sets as an informative exercise on ZDD

\def\set#1#2{\{#1\mid #2\} }

A FOS (= Family Of Sets) is, informally, a sorted list of sorted lists of ground prolog terms (called atoms).

ex1 {[], [a,b], [a,d], [c]}
ex2 {[], [a, d], [c(a)], [f(a, b), g(b)]}
ex3 {[]}
ex3 {}

For a list L, flatten/2 returns the list of all non-list terms appearing in L

?- flatten([[a, [b, [c,d]]], [[a]]], Y).
Y = [a, b, c, d, a].


It might be a good exercise to write a code, say zdd_flatten with analogy to the flatten/2 so that it returns a flat FOS Y for a given FOS X.

Y = \set {[x]} { x\in \alpha\; (\exists\alpha\in X)}

The problem is as easy as the flatten/2, but IMO, it requires a most basic understanding about ZDD.

A solution and query are below.

% ?- numlist(1, 100, Ns), zdd((X<<pow(Ns), shift(zdd_flatten(X, Y)), psa(Y))).
%
zdd_flatten(X, 0, _):- X<2, !.
zdd_flatten(X, Y, S):- memo(flatten(X)-Y, S),
(	nonvar(Y) -> true	% Many hits.
;	cofact(X, t(A, L, R), S),
zdd_flatten(L, L0, S),
zdd_flatten(R, R0, S),
zdd_join(L0, R0, Y0, S),
cofact(Y, t(A, Y0, 1), S)
).



This query should be reproducible in package pac-1.6.6 (latest) as follows.

% swipl
version 8.5.15-86-g5a3743ab9)

?- pack_install(pac).
?- use_module(library(pac)).
?- use_module(zdd(zdd)).
?- numlist(1, 100, Ns), zdd((X<<pow(Ns), shift(zdd_flatten(X, Y)), psa(Y))).
zid = 201
[100]
[99]
[98]

<snip>

[3]
[2]
[1]
-------------------
Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
X = 101,
Y = 201.



Although this tiny zdd_flatten might not appeal to the reader,
I wrote several other codes on FOS which were useful for solving some complex combinatorial problems. I wish I have time to post soon.