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><span style="font-family: courier new,monospace;">mnt :: [a] → [[a]] → [[a]]</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">mnt [] _ = []</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">mnt _ [] = []</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">mnt (x:xs) yss = map (x:) yss ++ mnt xs yss</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">pms :: [a] → Int → [[a]]</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">pms [] _ = [[]]</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">pms _ 0 = [[]]</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">pms xxs n = mnt xxs (pms xxs (n - 1))</span><br style="font-family: courier new,monospace;">
<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">Cetin Sert</b> <<a href="mailto:cetin.sert@gmail.com">cetin.sert@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;">
Thank you very much ^_^.<br><br>What would be a mathematically correct and understandable name for what we call 'pms' here?<br><br>And in what module do foldM, combine, replicate, rest, liftM and so on reside? How can I import them? o_O<br>
<span class="sg">
<br>-- Cetin Sert</span><div><span class="e" id="q_117b82ce3ec75f96_2"><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" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">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>
</span></div></blockquote></div><br>