Hi,
i am replying to a thread called "Data.List permutations" on ghc-
users and a thread called "powerSet = filterM (const [True,
False]) ... is this obfuscated haskell?" on haskell cafe.
On 04.08.2009, at 19:48, Slavomir Kaslev wrote:
A friend mine, new to functional programming, was entertaining
himself by
writing different combinatorial algorithms in Haskell. He asked me
for some
help so I sent him my quick and dirty solutions for generating
variations and
permutations:
On the haskell cafe thread it was observed that you can implement the
permutations function in a non-deterministic favour. The ideas behind
these implementations closely resemble implementations of
corresponding functions in Curry.
We can generalise your implementation to an arbitrary MonadPlus. The
idea is that the MonadPlus represents non-determinism. `inter` non-
deterministically inserts an element to every possible position of its
argument list.
inter x [] = [[x]]
inter x yys@(y:ys) = [x:yys] ++ map (y:) (inter x ys)
interM :: MonadPlus m => a -> [a] -> m [a]
interM x [] = return [x]
interM x yys@(y:ys) =
return (x:yys)
`mplus`
liftM (y:) (interM x ys)
perm [] = [[]]
perm (x:xs) = concatMap (inter x) (perm xs)
permM :: MonadPlus m => [a] -> m [a]
permM [] = return []
permM (x:xs) = interM x =<< permM xs
Alternatively we can implement permM by means of foldM.
permM :: MonadPlus m => [a] -> m [a]
permM = foldM (flip interM) []
A standard example for the use of non-determinism in Curry is a perm
function that looks very similar to `permM` with the slight difference
that you do not need the monad in Curry.
An alternative to this definition is to define a monadic version of
insertion sort. First we define a monadic equivalent of the `insertBy`
function as follows:
-- insertBy :: (a -> a -> Bool) -> a -> [a] -> [a]
-- insertBy _ x [] = [x]
-- insertBy le x (y:ys) =-- if le x y-- then x:y:ys
-- else y:insertBy le x ys
insertByM :: MonadPlus m => (a -> a -> m Bool) -> a -> [a] -> m [a]
insertByM _ x [] = return [x]
insertByM le x (y:ys) = do
b <- le x y
if b
then return (x:y:ys)
else liftM (y:) (insertByM le x ys)
Note that this function is very similar to interM, that is, we have
interM = insertByM (\_ _ -> return False `mplus` return True)
On basis of `insertBy` we can define insertion sort.
-- sortBy :: (a -> a -> Bool) -> [a] -> [a]
-- sortBy le = foldr (insertBy le) []
In the same manner we can define a function `sortByM` by means of
`insertByM`.
sortByM :: MonadPlus m => (a -> a -> m Bool) -> [a] -> m [a]
sortByM le = foldM (flip (insertByM le)) []
Now we can define a function that enumerates all permutations by means
of `sortByM`.
permM :: MonadPlus m => [a] -> m [a]
permM = sortByM (\_ _ -> return False `mplus` return True)
Interestingly we can also define permM by means of monadic
counterparts of other sorting algorithms like mergeSort. Although
there were some arguments on haskell cafe that this would not work for
other sorting algorithms it looks like this is not the case. At least
the corresponding implementation of perm by means of mergeSort in
Curry works well for lists that I can test in reasonable time.
Cheers, Jan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
