prologにはflattenがあるんだ…

rubyでついつい使っちゃうflatten

> [[1,2,3],[4,5,[6],7]].flatten
=> [1, 2, 3, 4, 5, 6, 7]

なんとprologにもあった。

?- flatten([1,2,3,[4,5,[],6],[7],8],X).
X = [1, 2, 3, 4, 5, 6, 7, 8].

もしかしたらflattenはprolog由来？（schemeには無かったしな）

?- help(flatten).
flatten(+List1, -List2)
    Transform  List1, possibly holding lists  as elements into a  `flat'
    list by replacing  each list with its elements (recursively).  Unify
    the resulting flat list with List2.  Example:

    ?- flatten([a, [b, [c, d], e]], X).

    X = [a, b, c, d, e]

true.

自分で書いてみる

append(X,[],X).
append(X,[Y|YS],[Y|Z]):-append(X,YS,Z).

flatten2([X|XS],A):-flatten2(X,Y),flatten2(XS,Z),append(Z,Y,A).
flatten2([],[]).
flatten2(X,[X]).

実行結果

?- flatten2([[1,2],3],X).
X = [1, 2, 3] .

?- flatten2([[1,2],3,[],4,[5,6,7]],X).
X = [1, 2, 3, 4, 5, 6, 7] .