Non-determinism, backtracking and Monads
Simon Peyton-Jones
simonpj@microsoft.com
Wed, 11 Jun 2003 09:03:32 +0100
Check out "Embedding Prolog in Haskell", which explores exactly the
topic you discuss.
http://citeseer.nj.nec.com/272378.html
Simon
| -----Original Message-----
| From: haskell-cafe-admin@haskell.org
[mailto:haskell-cafe-admin@haskell.org] On Behalf Of Graham
| Klyne
| Sent: 11 June 2003 08:38
| To: Jerzy Karczmarczuk; Haskell Cafe
| Subject: Non-determinism, backtracking and Monads
|=20
| At 11:06 05/06/03 +0200, Jerzy Karczmarczuk wrote:
| >I permit myself to observe that your powerset problem (and the
restricted
| >length problem, i.e. the combinations) is usually solved in Prolog,
through
| >backtracking, using reasoning/style which adopts this
"individualistic"
| >philosophy.
| >
| >powerset(<source>,<possible result>) --- is the pattern. And the
| >solution is
| >
| >powerset([],[]). Since nothing else can be done. Otherwise you pick
the item
| > or not.
| >
| >powerset([X|Rest],L) :- powerset(Rest,L).
| >powerset([X|Rest],[X|L) :- powerset(Rest,L).
| >
| >The xxx ++ map (x :) xxx solution in Haskell is a particular
formulation
| >(and optimization) of the straightforward transformation from a
version
| >using the non-deterministic Monad. This one is really almost a carbon
copy
| >of the Prolog solution, with appropriate "lifting" of operations from
| >individuals to lazy lists.
|=20
| I was thinking some more about this comment of yours, and my own
experience
| with the ease of using lists to implement prolog-style generators, and
| think I come to some better understanding. If I'm right, I assume the
| following is common knowledge to experienced Haskell programmers. So,
in
| the spirit of testing my understanding...
|=20
| The common thread here is a non-deterministic calculation in which
there
| are several possible solutions for some problem. The goal is to find
(a)
| if there are any solutions, and (b) one, more or all of the solutions.
|=20
| Prolog does this, absent ! (cut), by backtracking through the possible
| solutions.
|=20
| My first epiphany is that the Haskell idea of using a lazily evaluated
list
| for result of a non-deterministic computation is pretty much the same
thing
| (which is pretty much what you said? Is this what you mean by "the
| non-deterministic monad"?). The mechanisms for accessing a list mean
that
| the solutions must be accessed in the order they are generated, just
like
| Prolog backtracking.
|=20
| So there seems to be a very close relationship between the lazy list
and
| non-deterministic computations, but what about other data structures?
I
| speculate that other structures, lazily evaluated, may also be used to
| represent the results of non-deterministic computations, yet allow the
| results to be accessed in a different order. And these, too, may be
| (should be?) monads. If so, the Haskell approach might be viewed as a
| generalization of Prolog's essentially sequential backtracking.
|=20
| In a private message concerning the powerset thread on this list, a
| correspondent offered a program to evaluate the subsets in size order,
| which I found particularly elegant:
|=20
| >ranked_powerset :: [a] -> [[[a]]]
| >ranked_powerset =3D takeWhile (not . null) . foldr next_powerset =
([[]]
:
| repeat [])
| >
| >next_powerset :: a -> [[[a]]] -> [[[a]]]
| >next_powerset x r =3D zipWith (++) ([] : map (map (x:)) r) r
| >
| >powerset :: [a] -> [[a]]
| >powerset =3D tail . concat . ranked_powerset
|=20
| They also pointed out that "ranked_powerset is handy since you can use
it
| to define combinatorial choice etc.":
|=20
| > choose :: Int -> [a] -> [[a]]
| > choose k =3D (!! k) . ranked_powerset
|=20
| So here is an example of a different structure (a list of lists) also
used
| to represent a non-deterministic computation, and furthermore
providing
| means to access the results in some order other than a single linear
| sequences (e.g. could be used to enumerate all the powersets
containing the
| nth member of the base set, *or* all the powersets of a given size,
without
| evaluating all of the other powersets).
|=20
| To test this idea, I think it should be possible to define a monad
based on
| a simple tree structure, which also can be used to represent the
results of
| a non-deterministic computation. An example of this is below, at the
end
| of this message, which seems to exhibit the expected properties.
|=20
| So if the idea of representing a non-deterministic computation can be
| generalized from a list to a tree, why not to other data structures?
My
| tree monad is defined wholly in terms of reduce and fmap. Without
going
| through the exercise, I think the reduce function might be definable
in
| terms of fmap for any data type of the form "Type (Maybe a)", hence
| applicable to a range of functors? In particular, I'm wondering if it
can
| be applied to any gmap-able structure over a Maybe type.
|=20
| I'm not sure if this is of any practical use; rather it's part of my
| attempts to understand the relationship between functors and monads
and
| other things functional.
|=20
| #g
| --
|=20
|=20
| [[
| -- spike-treemonad.hs
|=20
| data Tree a =3D L (Maybe a) | T { l,r :: Tree a }
| deriving Eq
|=20
| instance (Show a) =3D> Show (Tree a) where
| show t =3D (showTree "" t) ++ "\n"
|=20
| showTree :: (Show a) =3D> String -> Tree a -> String
| showTree _ (L Nothing ) =3D "()"
| showTree _ (L (Just a)) =3D show a
| showTree i (T l r) =3D "( " ++ (showTree i' l) ++ "\n" ++
| i' ++ (showTree i' r) ++ " )"
| where i' =3D ' ':' ':i
|=20
| instance Functor Tree where
| fmap f (L Nothing) =3D L Nothing
| fmap f (L (Just a)) =3D L (Just (f a))
| fmap f (T l r) =3D T (fmap f l) (fmap f r)
|=20
| reduce :: Tree (Tree a) -> Tree a
| reduce (L Nothing) =3D L Nothing
| reduce (L (Just (L Nothing ) )) =3D L Nothing
| reduce (L (Just (L (Just a)) )) =3D L (Just a)
| reduce (L (Just (T l r ) )) =3D T l r
| reduce (T l r) =3D T (reduce l) (reduce r)
|=20
| instance Monad Tree where
| -- L Nothing >>=3D k =3D L Nothing
| t >>=3D k =3D reduce $ fmap k t
| return x =3D L (Just x)
| fail s =3D L Nothing
|=20
| -- tests
|=20
| t1 :: Tree String
| t1 =3D T (L $ Just "1")
| (T (T (T (L $ Just "211")
| (L $ Just "311"))
| (L Nothing))
| (L $ Just "22"))
|=20
| k1 :: a -> Tree a
| k1 n =3D T (L $ Just n) (L $ Just n)
|=20
| r1 =3D t1 >>=3D k1
|=20
| k2 :: String -> Tree String
| k2 s@('1':_) =3D L $ Just s
| k2 s@('2':_) =3D T (L $ Just s) (L $ Just s)
| k2 _ =3D L Nothing
|=20
| r2 =3D t1 >>=3D k2
|=20
| t3 =3D L Nothing :: Tree String
| r3 =3D t3 >>=3D k1
|=20
| r4 =3D t1 >>=3D k1 >>=3D k2
| r5 =3D (return "11") :: Tree String
| r6 =3D r5 >>=3D k1
|=20
| -- Check out monad laws
| -- return a >>=3D k =3D k a
| m1a =3D (return t1) >>=3D k1
| m1b =3D k1 t1
| m1c =3D m1a =3D=3D m1b
|=20
| -- m >>=3D return =3D m
| m2a =3D t1 >>=3D return
| m2b =3D t1
| m2c =3D m2a =3D=3D m2b
|=20
| -- m >>=3D (\x -> k x >>=3D h) =3D (m >>=3D k) >>=3D h
| m3a =3D t1 >>=3D (\x -> k1 x >>=3D k2)
| m3b =3D (t1 >>=3D k1) >>=3D k2
| m3c =3D m3a =3D=3D m3b
| ]]
|=20
|=20
| -------------------
| Graham Klyne
| <GK@NineByNine.org>
| PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
|=20
| _______________________________________________
| Haskell-Cafe mailing list
| Haskell-Cafe@haskell.org
| http://www.haskell.org/mailman/listinfo/haskell-cafe