Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/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. filter by max length a list of lists with equivalent values
(James Toll)
2. Re: filter by max length a list of lists with equivalent
values (Frerich Raabe)
3. Re: filter by max length a list of lists with equivalent
values (James Toll)
4. Re: filter by max length a list of lists with equivalent
values (Erlend Hamberg)
5. Re: filter by max length a list of lists with equivalent
values (James Toll)
6. Data.Stream interleave implementation question (Bryan Brady)
7. Re: Data.Stream interleave implementation question (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Tue, 11 Feb 2014 08:54:53 -0600
From: James Toll <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] filter by max length a list of lists with
equivalent values
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
Hi,
I have what?s proving to be a tricky little problem for me to solve. I?m
trying to take a list of a list of Int?s and return the longest list for each
list with elements of equivalent value. That?s not a great explanation, so let
me try to give an example:
If I have a list of lists grouped by element value.
ghci> group [1,1,1,1,2,2,2,2,3,3,2,2,2,5,6,2,2,7]
[[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[2,2],[7]]
I would like to take the subset of the outer list containing only the longest
of the inner lists for any particular element.
So for this particular example, the desired output would be:
[[1,1,1,1],[2,2,2,2],[3,3],[5],[6],[7]]
The lists [2,2,2] and [2,2] would be removed because they?re shorter than
[2,2,2,2].
Any thoughts on how to do this would be appreciated.
Thanks and best regards,
James
------------------------------
Message: 2
Date: Tue, 11 Feb 2014 16:08:40 +0100
From: Frerich Raabe <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] filter by max length a list of lists
with equivalent values
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
On 2014-02-11 15:54, James Toll wrote:
> If I have a list of lists grouped by element value.
>
> ghci> group [1,1,1,1,2,2,2,2,3,3,2,2,2,5,6,2,2,7]
> [[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[2,2],[7]]
>
> I would like to take the subset of the outer list containing only the
> longest of the inner lists for any particular element.
>
> So for this particular example, the desired output would be:
>
> [[1,1,1,1],[2,2,2,2],[3,3],[5],[6],[7]]
> Any thoughts on how to do this would be appreciated.
After grouping the given list, so that you have
[[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[2,2],[7]]
Sort the list by comparing the first element of each list
ghci> sortBy (comparing head)
[[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[2,2],[7]]
[[1,1,1,1],[2,2,2,2],[2,2,2],[2,2],[3,3],[5],[6],[7]]
Then, group that again such that lists with equal elements get put into
one list:
ghci> groupBy ((==) `on` head)
[[1,1,1,1],[2,2,2,2],[2,2,2],[2,2],[3,3],[5],[6],[7]]
[[[1,1,1,1]],[[2,2,2,2],[2,2,2],[2,2]],[[3,3]],[[5]],[[6]],[[7]]]
Finally, select the "maximum" of each inner list by comparing the
length of the sub-sub-lists:
ghci> map (maximumBy (comparing length))
[[[1,1,1,1]],[[2,2,2,2],[2,2,2],[2,2]],[[3,3]],[[5]],[[6]],[[7]]]
You'll need "Data.List", "Data.Ord" and "Data.Function" for this.
--
Frerich Raabe - [email protected]
www.froglogic.com - Multi-Platform GUI Testing
------------------------------
Message: 3
Date: Tue, 11 Feb 2014 09:34:31 -0600
From: James Toll <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] filter by max length a list of lists
with equivalent values
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
On Feb 11, 2014, at 9:08 AM, Frerich Raabe <[email protected]> wrote:
>
> After grouping the given list, so that you have
>
> [[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[2,2],[7]]
>
> Sort the list by comparing the first element of each list
>
> ghci> sortBy (comparing head)
> [[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[2,2],[7]]
> [[1,1,1,1],[2,2,2,2],[2,2,2],[2,2],[3,3],[5],[6],[7]]
>
> Then, group that again such that lists with equal elements get put into one
> list:
>
> ghci> groupBy ((==) `on` head)
> [[1,1,1,1],[2,2,2,2],[2,2,2],[2,2],[3,3],[5],[6],[7]]
> [[[1,1,1,1]],[[2,2,2,2],[2,2,2],[2,2]],[[3,3]],[[5]],[[6]],[[7]]]
>
> Finally, select the "maximum" of each inner list by comparing the length of
> the sub-sub-lists:
>
> ghci> map (maximumBy (comparing length))
> [[[1,1,1,1]],[[2,2,2,2],[2,2,2],[2,2]],[[3,3]],[[5]],[[6]],[[7]]]
Thank you for the nicely detailed explanation. In my frustration, I was
fearing I was going to have to revert to a more imperative approach to solving
this, and I was hoping someone would demonstrate a more functional solution.
In the various iterations that I unsuccessfully tried, I think the major idea I
was lacking was your second step, the groupBy ((==) `on` head). That?s really
the part I just wasn?t able to come up with on my own.
Again, thanks so much for the help.
Best,
James
------------------------------
Message: 4
Date: Tue, 11 Feb 2014 17:15:28 +0100
From: Erlend Hamberg <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] filter by max length a list of lists
with equivalent values
Message-ID:
<ca+g9oxmo2gmt3k0v8czzern55ucqpm+g7iddt+3v9muyxkh...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Another way to do this would be to sort the sub lists according to what
they contain (the list heads) and then their length (to resolve ties).
You could then use nubBy with "(==) `on` head" to remove lists and only be
left with the longest lists. Since nub[By] keeps only the first occurrence
of each element when there are duplicates, "comparing length" is flipped -
meaning that longer lists come first. This gives us the following function:
nubBy ((==) `on` head) . sortBy (comparing head <> flip (comparing
length)) . group
Where (<>) is from Data.Monoid. An explanation of using monoids to build
sorting combinators can be found in this reddit post [note that the author
uses (++) for (<>)]:
http://www.reddit.com/r/programming/comments/7cf4r/monoids_in_my_programming_language/c06adnx
--
Erlend Hamberg
[email protected]
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140211/1e27b245/attachment-0001.html>
------------------------------
Message: 5
Date: Tue, 11 Feb 2014 10:43:39 -0600
From: James Toll <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] filter by max length a list of lists
with equivalent values
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
On Feb 11, 2014, at 10:15 AM, Erlend Hamberg wrote:
> Another way to do this would be to sort the sub lists according to what they
> contain (the list heads) and then their length (to resolve ties).
> You could then use nubBy with ?(==) `on` head? to remove lists and only be
> left with the longest lists. Since nub[By] keeps only the first occurrence of
> each element when there are duplicates, ?comparing length? is flipped ?
> meaning that longer lists come first. This gives us the following function:
>
> nubBy ((==) `on` head) . sortBy (comparing head <> flip (comparing
> length)) . group
>
> Where (<>) is from Data.Monoid. An explanation of using monoids to build
> sorting combinators can be found in this reddit post [note that the author
> uses (++) for (<>)]:
> http://www.reddit.com/r/programming/comments/7cf4r/monoids_in_my_programming_language/c06adnx
Thank you for this example and the link. I have not explored the Data.Monoid
module yet, but I will read through the reddit post.
Best,
James
------------------------------
Message: 6
Date: Tue, 11 Feb 2014 23:23:05 -0500
From: Bryan Brady <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Data.Stream interleave implementation
question
Message-ID:
<cac2kvsqqld5k85_vpanlgtc9oarstewndnsvqb5nrssr4os...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I'm in the process of learning Haskell and am implementing my own Stream
type. ( I'm working my way through homework problems I found at
http://www.seas.upenn.edu/~cis194/hw/06-laziness.pdf )
One of the questions is:
"De?ne the stream
ruler :: Stream Integer
which corresponds to the ruler function
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, . . .
where the nth element in the stream (assuming the ?rst element
corresponds to n = 1) is the largest power of 2 which evenly
divides n. "
I got pretty close, but ended up looking at Data.Stream to nail down my
mistake. My original solution was:
-----
data Stream a = Cons a (Stream a) deriving (Eq, Ord)
streamRepeat :: a -> Stream a
streamRepeat a = Cons a (streamRepeat a)
interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Cons a as) (Cons b bs) = Cons a (Cons b
(interleaveStreams as bs))
ruler :: Stream Integer
ruler = foldr1 interleaveStreams (map streamRepeat [0..])
-----
Attempting to evaluate 'ruler' in ghci does not finish. I knew something
was wrong with my implementation of interleaveStreams because it worked
when I expanded it out manually for a few steps. The way Data.Stream
implements interleave is:
interleaveStreams (Cons a as) bs = Cons a (interleaveStreams bs as)
I don't understand why this works and why my original implementation
doesn't. I figure if the latter works, the former should as well. Here is
my reasoning:
In the latter definition, Cons a (interleaveStreams bs as),
(interleaveStreams bs as) is a thunk. The thunk should only be evaluated
when it is needed. In my original definition, (interleaveStreams as bs) is
a thunk. The difference is an extra Cons (e.g., Cons b). It seems like the
additional Cons is causing problems, I just don't understand why. Can
anyone point out what I'm missing?
thanks,
bb
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140211/a73d7f48/attachment-0001.html>
------------------------------
Message: 7
Date: Wed, 12 Feb 2014 15:10:21 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Data.Stream interleave implementation
question
Message-ID:
<CAPY+ZdS+DFk6PNhPHgtE0f9rvy7daveCFgu2J=fxa4q72od...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Wed, Feb 12, 2014 at 11:23 AM, Bryan Brady <[email protected]> wrote:
> ruler :: Stream Integer
> ruler = foldr1 interleaveStreams (map streamRepeat [0..])
>
This is an interesting solution.
I'd hazard to say that it's probably not the solution the author had in
mind, so bonus points for novelty!
How would you prove it correct though?
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140212/4e4b64a1/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 68, Issue 9
****************************************
