Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Custom partition lists into groups by providing group sizes using foldl (Apoorv Ingle) 2. Re: Custom partition lists into groups by providing group sizes using foldl (David Ringo) 3. Re: Custom partition lists into groups by providing group sizes using foldl (Apoorv Ingle) ---------------------------------------------------------------------- Message: 1 Date: Tue, 11 Jul 2017 14:26:04 -0700 From: Apoorv Ingle <apoorv.in...@gmail.com> To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <beginners@haskell.org> Subject: [Haskell-beginners] Custom partition lists into groups by providing group sizes using foldl Message-ID: <29c80a07-e2e0-40b8-af0f-c157555b3...@gmail.com> Content-Type: text/plain; charset="utf-8" Hi, I am trying to write a partition function where we pass group sizes and the list we want to partition into groups 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 {-# LANGUAGE ScopedTypeVariables #-} module Partition where partition :: [Int] -> [a] -> [[a]] partition ds ps = reverse $ paux ds ps [] where paux :: [Int] -> [a] -> [[a]] -> [[a]] paux [] [] ps' = ps' paux [] ps ps' = [ps] ++ ps’ paux _ [] ps' = ps' paux (d:ds') ps ps' = paux ds' (snd (splitAt d ps)) ([fst (splitAt d ps)] ++ ps') —————— *Partition> partition [2, 3] [1,2,3,4,5] [[1,2],[3,4,5]] *Partition> partition [1, 2] [1,2,3,4,5] [[1],[2,3],[4,5]] *Partition> partition [1, 2, 5] [1,2,3,4,5] [[1],[2,3],[4,5]] I was speculating if we could write the same function using foldl function but haven’t been able to figure it out. I would really appreciate if you can give me pointers on how we can implement it. partition' :: [Int] -> [a] -> [[a]] partition' [] ds = [ds] partition' ps ds = foldl ??? ???' ???'' contrary to my speculation is it even possible to write such a function using foldl if so why not? Regards, Apoorv Ingle Graduate Student, Computer Science apoorv.in...@ku.edu <mailto:apoorv.in...@ku.edu> -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.haskell.org/pipermail/beginners/attachments/20170711/ef9d12db/attachment-0001.html> ------------------------------ Message: 2 Date: Tue, 11 Jul 2017 22:40:04 +0000 From: David Ringo <davidmri...@gmail.com> To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <beginners@haskell.org> Subject: Re: [Haskell-beginners] Custom partition lists into groups by providing group sizes using foldl Message-ID: <CAPbyPx7bFzE8YJ2ndgc+E1y3SrGnLcWiOVC6bTT7GC=zcr3...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" Hi Apoorv, There is indeed a left fold: foldlpart :: [Int] -> [a] -> [[a]] foldlpart ds ps = result where result | null remaining = initial | otherwise = initial ++ [remaining] (initial, remaining) = foldl aux ([], ps) ds aux (l, xs) d = case xs of [] -> (l, xs) _ -> let (f,s) = splitAt d xs in (l ++ [f], s) I'm sure someone else can put something better together though. I much prefer this right fold, since it avoids quadratic behavior incurred with (++) above: foldrpart :: [Int] -> [a] -> [[a]] foldrpart ds ps = myFunc ps where myFunc = foldr buildMyFunc (: []) ds buildMyFunc digit func = \ps -> case ps of [] -> [] _ -> let (first, last) = splitAt digit ps in first : func last 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 to take from some list. Hope this is useful. - David On Tue, Jul 11, 2017 at 3:30 PM Apoorv Ingle <apoorv.in...@gmail.com> wrote: > Hi, > > I am trying to write a partition function where we pass group sizes and > the list we want to partition into groups > 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 > > {-# LANGUAGE ScopedTypeVariables #-} > > module Partition where > > partition :: [Int] -> [a] -> [[a]] > partition ds ps = reverse $ paux ds ps [] > where > paux :: [Int] -> [a] -> [[a]] -> [[a]] > paux [] [] ps' = ps' > paux [] ps ps' = [ps] ++ ps’ > paux _ [] ps' = ps' > paux (d:ds') ps ps' = paux ds' (snd (splitAt d ps)) ([fst (splitAt d > ps)] ++ ps') > > —————— > > > *Partition> partition [2, 3] [1,2,3,4,5] > [[1,2],[3,4,5]] > *Partition> partition [1, 2] [1,2,3,4,5] > [[1],[2,3],[4,5]] > *Partition> partition [1, 2, 5] [1,2,3,4,5] > [[1],[2,3],[4,5]] > > > > I was speculating if we could write the same function using foldl function > but haven’t been able to figure it out. > I would really appreciate if you can give me pointers on how we can > implement it. > > partition' :: [Int] -> [a] -> [[a]] > partition' [] ds = [ds] > partition' ps ds = foldl ??? ???' ???'' > > > contrary to my speculation is it even possible to write such a function > using foldl if so why not? > > Regards, > Apoorv Ingle > Graduate Student, Computer Science > apoorv.in...@ku.edu > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.haskell.org/pipermail/beginners/attachments/20170711/dd88c042/attachment-0001.html> ------------------------------ Message: 3 Date: Tue, 11 Jul 2017 16:18:53 -0700 From: Apoorv Ingle <apoorv.in...@gmail.com> To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <beginners@haskell.org> Subject: Re: [Haskell-beginners] Custom partition lists into groups by providing group sizes using foldl Message-ID: <219defed-7988-472d-90d9-68b74fa4a...@gmail.com> Content-Type: text/plain; charset="utf-8" Hi David, Thanks a lot for the code! foldr is indeed elegant. In general is it advisable to use auxiliary functions or foldr/foldl variations. Does it have any performance benefits or ghc would generate same core language for both the functions? Regards, Apoorv > On Jul 11, 2017, at 15:40, David Ringo <davidmri...@gmail.com> wrote: > > Hi Apoorv, > > There is indeed a left fold: > > foldlpart :: [Int] -> [a] -> [[a]] > foldlpart ds ps = result > where result | null remaining = initial > | otherwise = initial ++ [remaining] > (initial, remaining) = foldl aux ([], ps) ds > aux (l, xs) d = case xs of > [] -> (l, xs) > _ -> let (f,s) = splitAt d xs in (l ++ [f], s) > > I'm sure someone else can put something better together though. > > I much prefer this right fold, since it avoids quadratic behavior incurred > with (++) above: > > foldrpart :: [Int] -> [a] -> [[a]] > foldrpart ds ps = myFunc ps > where myFunc = foldr buildMyFunc (: []) ds > buildMyFunc digit func = \ps -> > case ps of > [] -> [] > _ -> let (first, last) = splitAt digit ps > in first : func last > > 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 > to take from some list. > > Hope this is useful. > > - David > > On Tue, Jul 11, 2017 at 3:30 PM Apoorv Ingle <apoorv.in...@gmail.com > <mailto:apoorv.in...@gmail.com>> wrote: > Hi, > > I am trying to write a partition function where we pass group sizes and the > list we want to partition into groups > 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 > > {-# LANGUAGE ScopedTypeVariables #-} > > module Partition where > > partition :: [Int] -> [a] -> [[a]] > partition ds ps = reverse $ paux ds ps [] > where > paux :: [Int] -> [a] -> [[a]] -> [[a]] > paux [] [] ps' = ps' > paux [] ps ps' = [ps] ++ ps’ > paux _ [] ps' = ps' > paux (d:ds') ps ps' = paux ds' (snd (splitAt d ps)) ([fst (splitAt d ps)] > ++ ps') > > —————— > > *Partition> partition [2, 3] [1,2,3,4,5] > [[1,2],[3,4,5]] > *Partition> partition [1, 2] [1,2,3,4,5] > [[1],[2,3],[4,5]] > *Partition> partition [1, 2, 5] [1,2,3,4,5] > [[1],[2,3],[4,5]] > > > I was speculating if we could write the same function using foldl function > but haven’t been able to figure it out. > I would really appreciate if you can give me pointers on how we can implement > it. > > partition' :: [Int] -> [a] -> [[a]] > partition' [] ds = [ds] > partition' ps ds = foldl ??? ???' ???'' > > contrary to my speculation is it even possible to write such a function using > foldl if so why not? > > Regards, > Apoorv Ingle > Graduate Student, Computer Science > apoorv.in...@ku.edu > <mailto:apoorv.in...@ku.edu>_______________________________________________ > Beginners mailing list > Beginners@haskell.org <mailto:Beginners@haskell.org> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners > <http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners> > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.haskell.org/pipermail/beginners/attachments/20170711/a12a35cc/attachment.html> ------------------------------ Subject: Digest Footer _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners ------------------------------ End of Beginners Digest, Vol 109, Issue 13 ******************************************