extra/rosetta-code/amb/amb.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: backtrack continuations kernel prettyprint sequences
   4 splitting ;
   5 IN: rosetta-code.amb
   6
   7 ! http://rosettacode.org/wiki/Amb
   8
   9 ! Define and give an example of the Amb operator.
  10
  11 ! The Amb operator takes some number of expressions (or values
  12 ! if that's simpler in the language) and nondeterministically
  13 ! yields the one or fails if given no parameter, amb returns the
  14 ! value that doesn't lead to failure.
  15
  16 ! The example is using amb to choose four words from the following strings:
  17
  18 ! set 1: "the" "that" "a"
  19 ! set 2: "frog" "elephant" "thing"
  20 ! set 3: "walked" "treaded" "grows"
  21 ! set 4: "slowly" "quickly"
  22
  23 ! It is a failure if the last character of word 1 is not equal
  24 ! to the first character of word 2, and similarly with word 2 and
  25 ! word 3, as well as word 3 and word 4. (the only successful
  26 ! sentence is "that thing grows slowly").
  27
  28 CONSTANT: words {
  29     { "the" "that" "a" }
  30     { "frog" "elephant" "thing" }
  31     { "walked" "treaded" "grows" }
  32     { "slowly" "quickly"  }
  33 }
  34
  35 : letters-match? ( str1 str2 -- ? ) [ last ] [ first ] bi* = ;
  36
  37 : sentence-match? ( seq -- ? ) dup rest [ letters-match? ] 2all? ;
  38
  39 : select ( seq -- seq' ) [ amb-lazy ] map ;
  40
  41 : search ( -- )
  42     words select dup sentence-match? [ join-words ] [ fail ] if . ;
  43
  44 MAIN: search