Hello again Ryan,<br><br>I have found out where to import those stuff from and tested your more elegant suggestion and my original performance.<br><br><span style="font-family: courier new,monospace;">-- print ((length ∘ pmsO [0,1]) 24) 9~ seconds</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">-- print ((length ∘ pmsE [0,1]) 24) 23~ seconds</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">-- print ((length ∘ pmsU [0,1]) 24) 23~ seconds</span><br style="font-family: courier new,monospace;">
<br>-- O: original, E: elegant, U: unreadable<br><br>I prefer performance over elegance (and for me using monads almost feels like adding an unnecessary dependency to the definition of pms. Though I know I may be dead wrong on that. I just don't quite understand monads yet.)<br>
<br>I would love to have you and/or others suggest more performant versions of pms (and maybe also come up with a better name for it).<br><br>mnt :: [a] → [[a]] → [[a]]<br>mnt [] _ = []<br>mnt _ [] = []<br>mnt (x:xs) yss = map (x:) yss ++ mnt xs yss<br>
<br>pms :: [a] → Int → [[a]]<br>pms [] _ = [[]]<br>pms _ 0 = [[]]<br>pms xxs n = mnt xxs (pms xxs (n - 1))<br><br>I generalized 'pms' from the 'bools' function on page 108 of Programming in Haskell (Hutton, 2007)<br>
<br>-- Cetin Sert<br><br><div><span class="gmail_quote">On 26/01/2008, <b class="gmail_sendername">Ryan Ingram</b> <<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
When you say permuations, I think of reorderings of a list, for example:<br><br>permutations [1,2,3] =<br>[ [1,2,3],<br> [1,3,2],<br> [2,1,3],<br> [2,3,1],<br> [3,1,2],<br> [3,2,1] ]<br><br>Here's an implementation:<br>
<br>-- split [1,2,3] => [<br>-- ( 1, [2,3] ),<br>-- ( 2, [1,3] ),<br>-- ( 3, [1,2] ) ]<br>split :: [a] -> [(a, [a])]<br>split [] = error "split: empty list"<br>split [a] = [(a, [])]<br>split (a:as) = (a, as) : map prefix (split as)<br>
where prefix (x, xs) = (x, a : xs)<br><br>permutations :: [a] -> [[a]]<br>permutations [] = return []<br>permutations xs = do<br> (first, rest) <- split xs<br> rest' <- permutations rest<br> return (first : rest')<br>
<br>The problem you solved can be solved much more elegantly:<br><br>pms : [a] -> Int -> [[a]]<br>pms xs n = foldM combine [] (replicate n xs) where<br> combine rest as = liftM (:rest) as<br><br>or, for the unreadable version:<br>
pms xs n = foldM (map . flip (:)) [] $ replicate n xs<br><br>(note that, in the list monad, liftM = map).<br><br> -- ryan<br></blockquote></div><br>