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. Re: Majority Element (Andrew Wagner)
2. Re: A better way? (Patrick LeBoutillier)
3. Re: A better way? (Keith Sheppard)
4. Re: Baffled by Parsec (Colin Paul Adams)
5. Re: Baffled by Parsec (Felipe Lessa)
6. Re: Baffled by Parsec (Colin Paul Adams)
7. Re: Baffled by Parsec (Felipe Lessa)
8. Re: Baffled by Parsec (Colin Paul Adams)
----------------------------------------------------------------------
Message: 1
Date: Sat, 21 Feb 2009 20:20:43 -0500
From: Andrew Wagner <[email protected]>
Subject: Re: [Haskell-beginners] Majority Element
To: "Matthew J. Williams" <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
I've never heard this term. Can you give some context?
On Sat, Feb 21, 2009 at 8:15 PM, Matthew J. Williams <
[email protected]> wrote:
> Dear listers
>
> What is a majority element in an array?
>
> Sincerely
> Matthew J. Williams
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090221/ef1e1c3d/attachment-0001.htm
------------------------------
Message: 2
Date: Sat, 21 Feb 2009 21:32:09 -0500
From: Patrick LeBoutillier <[email protected]>
Subject: Re: [Haskell-beginners] A better way?
To: Daniel Fischer <[email protected]>
Cc: Keith Sheppard <[email protected]>, [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi,
I changed my code to :
maxTableColumnWidths :: [[String]] -> [Int]
maxTableColumnWidths = foldl' rowMax zeros
where rowMax = zipWith (\m f -> max (length f) m)
zeros = 0 : zeros
but it still blows the stack. I don't understand why. Doesn't foldl'
force the evaluation of each call to rowMax? If so then I don't see
what causes the stack to get so big... unless I'm looking in the wrong
place...
Can anyone shed some light?
Patrick
On Sat, Feb 21, 2009 at 8:03 PM, Daniel Fischer
<[email protected]> wrote:
> Am Sonntag, 22. Februar 2009 01:32 schrieb Keith Sheppard:
>> ghci still is not happy if we have many rows...
>>
>> Prelude> :load Table.IO
>> [1 of 1] Compiling Table.IO ( Table/IO.hs, interpreted )
>> Ok, modules loaded: Table.IO.
>> *Table.IO> let maxTableColumnWidths = foldr ((evalList .) . zipWithD
>> max) [] . map (map length)
>> *Table.IO> let maxTCWs = evalList . foldr (zipWithD max) [] . map (map
>> length) *Table.IO> maxTableColumnWidths (replicate 1000000 ["hello",
>> "world"]) *** Exception: stack overflow
>
> Yes, foldr was the wrong choice. make it foldl' (don't forget the prime at the
> end) and it works for large tables. If the rows are short, it actually is
> faster (here) than your version, but if the rows are long , e.g.
>
> maxTableColumnWidths (replicate 2000 (replicate 1000 "what?"))
>
> your version is faster than
>
> import Data.List (foldl')
>
> seqList [] = False
> seqList (head:tail)
> | head `seq` False = undefined
> | otherwise = seqList tail
>
> evalList xs
> | seqList xs = undefined
> | otherwise = xs
>
> zipWithD :: (a -> a -> a) -> [a] -> [a] -> [a]
> zipWithD f (x:xt) (y:yt) = f x y:zipWithD f xt yt
> zipWithD _ [] ys = ys
> zipWithD _ xs [] = xs
>
> maxTableColumnWidths =
> foldl' ((evalList .) . zipWithD max) [] . map (map length)
>
>
>> *Table.IO> maxTCWs (replicate 1000000 ["hello", "world"])
>> *** Exception: stack overflow
>
> That doesn't surprise me in the least. One has to force the list in each step.
>
>>
>> I hadn't thought of using ByteStrings since I don't know what they are
>
> ByteStrings are basically byte arrays. Thus if you're dealing exclusively with
> characters in the range 0-255, you need only one byte per character, while
> with Strings, you need four bytes for each character itself, plus several
> machine words for pointers (list cell to Char, list cell to next), I don't
> remember, but I think it amounts to 12 or 20 bytes per character.
>>
>> :-). I'll have to look into it, but I'm assuming that ByteStrings will
>>
>> give some constant time/space improvement?
>
> Can be several orders of magnitude faster, and as said above, they use far
> less memory (but they're useful only for long enough strings, having a
> multitude of short ByteStrings floating around doesn't do any good).
>
>> I think it won't help with
>> my first problem though since what's happening is that the lazy
>> function calls are piling up too deep (at least thats what I think is
>> happening).
>
> Yes, that's basically what *** Exception: stack overflow means :)
>
>>
>> Thank you
>> Keith
>>
>
> Cheers,
> Daniel
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
--
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada
------------------------------
Message: 3
Date: Sat, 21 Feb 2009 21:38:07 -0500
From: Keith Sheppard <[email protected]>
Subject: Re: [Haskell-beginners] A better way?
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Thanks, this code looks cleaner than what I had. I like how zipWithD
fixes the whole issue of uneven rows...
-Keith
On Sat, Feb 21, 2009 at 8:03 PM, Daniel Fischer
<[email protected]> wrote:
> Am Sonntag, 22. Februar 2009 01:32 schrieb Keith Sheppard:
>> ghci still is not happy if we have many rows...
>>
>> Prelude> :load Table.IO
>> [1 of 1] Compiling Table.IO ( Table/IO.hs, interpreted )
>> Ok, modules loaded: Table.IO.
>> *Table.IO> let maxTableColumnWidths = foldr ((evalList .) . zipWithD
>> max) [] . map (map length)
>> *Table.IO> let maxTCWs = evalList . foldr (zipWithD max) [] . map (map
>> length) *Table.IO> maxTableColumnWidths (replicate 1000000 ["hello",
>> "world"]) *** Exception: stack overflow
>
> Yes, foldr was the wrong choice. make it foldl' (don't forget the prime at the
> end) and it works for large tables. If the rows are short, it actually is
> faster (here) than your version, but if the rows are long , e.g.
>
> maxTableColumnWidths (replicate 2000 (replicate 1000 "what?"))
>
> your version is faster than
>
> import Data.List (foldl')
>
> seqList [] = False
> seqList (head:tail)
> | head `seq` False = undefined
> | otherwise = seqList tail
>
> evalList xs
> | seqList xs = undefined
> | otherwise = xs
>
> zipWithD :: (a -> a -> a) -> [a] -> [a] -> [a]
> zipWithD f (x:xt) (y:yt) = f x y:zipWithD f xt yt
> zipWithD _ [] ys = ys
> zipWithD _ xs [] = xs
>
> maxTableColumnWidths =
> foldl' ((evalList .) . zipWithD max) [] . map (map length)
>
>
>> *Table.IO> maxTCWs (replicate 1000000 ["hello", "world"])
>> *** Exception: stack overflow
>
> That doesn't surprise me in the least. One has to force the list in each step.
>
>>
>> I hadn't thought of using ByteStrings since I don't know what they are
>
> ByteStrings are basically byte arrays. Thus if you're dealing exclusively with
> characters in the range 0-255, you need only one byte per character, while
> with Strings, you need four bytes for each character itself, plus several
> machine words for pointers (list cell to Char, list cell to next), I don't
> remember, but I think it amounts to 12 or 20 bytes per character.
>>
>> :-). I'll have to look into it, but I'm assuming that ByteStrings will
>>
>> give some constant time/space improvement?
>
> Can be several orders of magnitude faster, and as said above, they use far
> less memory (but they're useful only for long enough strings, having a
> multitude of short ByteStrings floating around doesn't do any good).
>
>> I think it won't help with
>> my first problem though since what's happening is that the lazy
>> function calls are piling up too deep (at least thats what I think is
>> happening).
>
> Yes, that's basically what *** Exception: stack overflow means :)
>
>>
>> Thank you
>> Keith
>>
>
> Cheers,
> Daniel
>
>
------------------------------
Message: 4
Date: Sun, 22 Feb 2009 07:23:37 +0000
From: Colin Paul Adams <[email protected]>
Subject: Re: [Haskell-beginners] Baffled by Parsec
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>>>>> "Daniel" == Daniel Fischer <[email protected]> writes:
Thanks.
In fact all I need is:
parse_integer :: Parser Int
parse_integer = do
digits <- many1 digit
let n = read digits
return n
as the format does not permit a sign.
What I was missing was digits. Where does it come from? I can't find
it with Hoggle.
--
Colin Adams
Preston Lancashire
------------------------------
Message: 5
Date: Sun, 22 Feb 2009 04:37:09 -0300
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] Baffled by Parsec
To: Colin Paul Adams <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sun, Feb 22, 2009 at 4:23 AM, Colin Paul Adams
<[email protected]> wrote:
> parse_integer :: Parser Int
> parse_integer = do
> digits <- many1 digit
> let n = read digits
> return n
'digits' come from 'digits <- many1 digit', and 'digit' comes from
Parsec itself[1] (and is the same as 'satisfy isDigit'[2,3]). I should
note that it is more idiomatic to write 'parse_integer' as
> import Control.Monad (liftM)
>
> parse_integer :: Parse Int
> parse_integer = read `liftM` many1 digit
if you don't need signs.
HTH,
[1]
http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-Parsec-Char.html#v%3Adigit
[2]
http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/src/Text-Parsec-Char.html#digit
[3]
http://hackage.haskell.org/packages/archive/base/4.0.0.0/doc/html/Data-Char.html#v%3AisDigit
--
Felipe.
------------------------------
Message: 6
Date: Sun, 22 Feb 2009 07:50:40 +0000
From: Colin Paul Adams <[email protected]>
Subject: Re: [Haskell-beginners] Baffled by Parsec
To: Felipe Lessa <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>>>>> "Felipe" == Felipe Lessa <[email protected]> writes:
Felipe> On Sun, Feb 22, 2009 at 4:23 AM, Colin Paul Adams
Felipe> <[email protected]> wrote:
>> parse_integer :: Parser Int parse_integer = do digits <- many1
>> digit let n = read digits return n
Felipe> 'digits' come from 'digits <- many1 digit', and 'digit'
Felipe> comes from Parsec itself[1] (and is the same as 'satisfy
Thanks. I meant digit, not digits.
Felipe> [1]
Felipe>
http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-Parsec-Char.html#v%3Adigit
OK - I see it here, but I was looking in
Text.ParserCombinators.Parsec.Char, where I can't see it (I can see
satisfy). I can't see how I am supposed to make that apparently
disconnected leap (other than by asking here, which works :-) )
--
Colin Adams
Preston Lancashire
------------------------------
Message: 7
Date: Sun, 22 Feb 2009 04:53:15 -0300
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] Baffled by Parsec
To: Colin Paul Adams <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sun, Feb 22, 2009 at 4:50 AM, Colin Paul Adams
<[email protected]> wrote:
> OK - I see it here, but I was looking in
> Text.ParserCombinators.Parsec.Char, where I can't see it (I can see
> satisfy). I can't see how I am supposed to make that apparently
> disconnected leap (other than by asking here, which works :-) )
It is there, too! =P
http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-ParserCombinators-Parsec-Char.html#v%3Adigit
--
Felipe.
------------------------------
Message: 8
Date: Sun, 22 Feb 2009 08:02:13 +0000
From: Colin Paul Adams <[email protected]>
Subject: Re: [Haskell-beginners] Baffled by Parsec
To: Felipe Lessa <[email protected]>
Cc: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>>>>> "Felipe" == Felipe Lessa <[email protected]> writes:
Felipe> On Sun, Feb 22, 2009 at 4:50 AM, Colin Paul Adams
Felipe> <[email protected]> wrote:
>> OK - I see it here, but I was looking in
>> Text.ParserCombinators.Parsec.Char, where I can't see it (I can
>> see satisfy). I can't see how I am supposed to make that
>> apparently disconnected leap (other than by asking here, which
>> works :-) )
Felipe> It is there, too! =P
Felipe>
http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-ParserCombinators-Parsec-Char.html#v%3Adigit
Hm.
It's not on my local copy of the GHC libraries documentation (ghc
6.10.1), although if I click the source button, I can see it.
--
Colin Adams
Preston Lancashire
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 20
****************************************
