[Haskell-beginners] A better way?

[Patrick LeBoutillier]

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
<daniel.is.fischer at web.de> 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
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



-- 
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada