Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
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 <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Custom partition lists into groups by
providing group sizes using foldl
Message-ID: <[email protected]>
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
[email protected] <mailto:[email protected]>
-------------- 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 <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
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 <[email protected]> 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
> [email protected]
> _______________________________________________
> Beginners mailing list
> [email protected]
> 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 <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Custom partition lists into groups by
providing group sizes using foldl
Message-ID: <[email protected]>
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 <[email protected]> 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 <[email protected]
> <mailto:[email protected]>> 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
> [email protected]
> <mailto:[email protected]>_______________________________________________
> Beginners mailing list
> [email protected] <mailto:[email protected]>
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> <http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners>
> _______________________________________________
> Beginners mailing list
> [email protected]
> 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
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 109, Issue 13
******************************************
