Amb

editable example

Click the pencil to open this in an editor, change it, and run it in your browser. The same solution is posted on Rosetta Code.

ghul

use IO.Std.write_line

use Collections.Iterable

use Collections.List

use Collections.LIST

use Ghul.Pipes

amb[T](

sets: List[Iterable[T]],

accepts: (T, T) -> bool pure

) -> Pipe[LIST[T]] is

if sets.count == 0 then

yield LIST[T]()

else

for choice in sets[0] do

for rest in amb(sets |> skip(1) |> collect(), accepts) do

if rest.count == 0 \/ accepts(choice, rest[0]) then

let sequence = LIST[T]()

sequence.add(choice)

sequence.add_range(rest)

yield sequence

fi

od

od

fi

si

let sets: List[Iterable[string]] = [

["the", "that", "a"],

["frog", "elephant", "thing"],

["walked", "treaded", "grows"],

["slowly", "quickly"]

]

let joins =

(left: string, right: string) => left[left.length - 1] == right[0]

for sentence in amb(sets, joins) do

write_line(sentence |> join(" "))

od

that thing grows slowly