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