<div dir="ltr">I know that there are specialization rules for foldl and foldr (among other higher-order functions in the Prelude) with the idea that they will produce usually better generated code. So, yes, the generated Core will almost certainly be different. <div><br></div><div>Whether the code is truly more performant (in time or space) will likely depend on your use case. Inspecting the Core manually may give you some insights, but unless you're experienced in that domain, you'll get more direct and faster answers by using GHC's profiling tools with some chosen benchmarks.</div><div><br></div><div>- David</div></div><br><div class="gmail_quote"><div dir="ltr">On Tue, Jul 11, 2017 at 5:20 PM Apoorv Ingle <<a href="mailto:apoorv.ingle@gmail.com">apoorv.ingle@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div>Hi David,</div><div><br></div><div>Thanks a lot for the code!</div><div><br></div><div>foldr is indeed elegant.</div><div><div>In general is it advisable to use auxiliary functions or foldr/foldl variations.</div><div>Does it have any performance benefits or ghc would generate same core language for both the functions?</div><div><br></div><div>Regards,</div><div>Apoorv</div></div></div><div style="word-wrap:break-word"><div><br></div><div><blockquote type="cite"><div>On Jul 11, 2017, at 15:40, David Ringo <<a href="mailto:davidmringo@gmail.com" target="_blank">davidmringo@gmail.com</a>> wrote:</div><br class="m_2112206603626404561Apple-interchange-newline"><div><div dir="ltr">Hi Apoorv,<div><br></div><div>There is indeed a left fold:</div><div><br></div><div><div><font face="monospace">foldlpart :: [Int] -> [a] -> [[a]]<br></font></div><div><font face="monospace">foldlpart ds ps = result</font></div><div><font face="monospace"> where result | null remaining = initial</font></div><div><font face="monospace"> | otherwise = initial ++ [remaining]</font></div><div><font face="monospace"> (initial, remaining) = foldl aux ([], ps) ds</font></div><div><font face="monospace"> aux (l, xs) d = case xs of</font></div><div><font face="monospace"> [] -> (l, xs)</font></div><div><font face="monospace"> _ -> let (f,s) = splitAt d xs in (l ++ [f], s)</font></div><div><br></div><div>I'm sure someone else can put something better together though.</div><div><br></div><div>I much prefer this right fold, since it avoids quadratic behavior incurred with (++) above:</div><div><br></div><div><div><font face="monospace">foldrpart :: [Int] -> [a] -> [[a]]</font></div><div><font face="monospace">foldrpart ds ps = myFunc ps</font></div><div><font face="monospace"> where myFunc = foldr buildMyFunc (: []) ds</font></div><div><font face="monospace"> buildMyFunc digit func = \ps -></font></div><div><font face="monospace"> case ps of</font></div><div><font face="monospace"> [] -> []</font></div><div><font face="monospace"> _ -> let (first, last) = splitAt digit ps</font></div><div><font face="monospace"> in first : func last</font></div></div><div><br></div><div>If it's unclear, buildMyFunc is basically composing a bunch of functions which know (from the fold on the list of Ints) how many elements</div><div>to take from some list.</div><div><br></div><div>Hope this is useful.</div><div><br></div><div>- David</div><div><br><div class="gmail_quote"><div dir="ltr">On Tue, Jul 11, 2017 at 3:30 PM Apoorv Ingle <<a href="mailto:apoorv.ingle@gmail.com" target="_blank">apoorv.ingle@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div>Hi,</div><div><br></div><div>I am trying to write a partition function where we pass group sizes and the list we want to partition into groups </div><div>as arguments and get back a list of groups (or list of lists in this case). My first attempt was by using an auxiliary inner function</div><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font color="#0056d6">{-# LANGUAGE ScopedTypeVariables #-}</font></div></div><div><div><font color="#0056d6"><br></font></div></div><div><div><font color="#0056d6">module Partition where</font></div></div><div><font color="#0056d6"><br></font></div><div><div><div><font color="#0056d6">partition :: [Int] -> [a] -> [[a]]</font></div></div></div><div><div><div><font color="#0056d6">partition ds ps = reverse $ paux ds ps []</font></div></div></div><div><div><div><font color="#0056d6"> where</font></div></div></div><div><div><div><font color="#0056d6"> </font><span style="color:rgb(0,86,214)">paux</span><font color="#0056d6"> :: [Int] -> [a] -> [[a]] -> [[a]]</font></div></div></div><div><div><div><font color="#0056d6"> </font><span style="color:rgb(0,86,214)">paux</span><font color="#0056d6"> [] [] ps' = ps'</font></div></div></div><div><div><div><font color="#0056d6"> </font><span style="color:rgb(0,86,214)">paux</span><font color="#0056d6"> [] ps ps' = [ps] ++ ps’ </font></div></div></div><div><div><div><font color="#0056d6"> </font><span style="color:rgb(0,86,214)">paux</span><font color="#0056d6"> _ [] ps' = ps'</font></div></div></div><div><div><div><font color="#0056d6"> </font><span style="color:rgb(0,86,214)">paux</span><font color="#0056d6"> (d:ds') ps ps' = </font><span style="color:rgb(0,86,214)">paux</span><font color="#0056d6"> ds' (snd (splitAt d ps)) ([fst (split</font><span style="color:rgb(0,86,214)">At d ps)] ++ ps')</span></div></div></div><div><font color="#0056d6"><br></font></div></blockquote>——————<br><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><font color="#0056d6"><br></font></div><div><div><div><font color="#0056d6">*Partition> partition [2, 3] [1,2,3,4,5]</font></div></div></div><div><div><div><font color="#0056d6">[[1,2],[3,4,5]]</font></div></div></div><div><div><div><font color="#0056d6">*Partition> partition [1, 2] [1,2,3,4,5]</font></div></div></div><div><div><div><font color="#0056d6">[[1],[2,3],[4,5]]</font></div></div></div><div><div><div><font color="#0056d6">*Partition> partition [1, 2, 5] [1,2,3,4,5]</font></div></div></div><div><div><div><font color="#0056d6">[[1],[2,3],[4,5]]</font></div></div></div></blockquote><div><div><br></div><div><br></div><div>I was speculating if we could write the same function using foldl function but haven’t been able to figure it out.</div><div>I would really appreciate if you can give me pointers on how we can implement it.</div><div><br></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font color="#0056d6">partition' :: [Int] -> [a] -> [[a]]</font></div></div><div><div><font color="#0056d6">partition' [] ds = [ds]</font></div></div><div><div><font color="#0056d6">partition' ps ds = foldl ??? ???' ???''</font></div></div></blockquote><div><br></div><div>contrary to my speculation is it even possible to write such a function using foldl if so why not?</div><div><br></div>Regards,<br><div><div style="word-wrap:break-word">Apoorv Ingle<br>Graduate Student, Computer Science<br><a href="mailto:apoorv.ingle@ku.edu" target="_blank">apoorv.ingle@ku.edu</a></div></div></div>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div></div></div></div>
_______________________________________________<br>Beginners mailing list<br><a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br></div></blockquote></div><br></div>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div>