[Haskell-cafe] Re: Generic permutations
cetin.sert at gmail.com
Sat Jan 26 17:17:05 EST 2008
Thank you very much ^_^.
What would be a mathematically correct and understandable name for what we
call 'pms' here?
And in what module do foldM, combine, replicate, rest, liftM and so on
reside? How can I import them? o_O
-- Cetin Sert
On 26/01/2008, Ryan Ingram <ryani.spam at gmail.com> wrote:
> When you say permuations, I think of reorderings of a list, for example:
> permutations [1,2,3] =
> [ [1,2,3],
> [3,2,1] ]
> Here's an implementation:
> -- split [1,2,3] => [
> -- ( 1, [2,3] ),
> -- ( 2, [1,3] ),
> -- ( 3, [1,2] ) ]
> split :: [a] -> [(a, [a])]
> split  = error "split: empty list"
> split [a] = [(a, )]
> split (a:as) = (a, as) : map prefix (split as)
> where prefix (x, xs) = (x, a : xs)
> permutations :: [a] -> [[a]]
> permutations  = return 
> permutations xs = do
> (first, rest) <- split xs
> rest' <- permutations rest
> return (first : rest')
> The problem you solved can be solved much more elegantly:
> pms : [a] -> Int -> [[a]]
> pms xs n = foldM combine  (replicate n xs) where
> combine rest as = liftM (:rest) as
> or, for the unreadable version:
> pms xs n = foldM (map . flip (:))  $ replicate n xs
> (note that, in the list monad, liftM = map).
> -- ryan
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe