Stack overflow folding a map

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Stack overflow folding a map

tcollin371
I've been playing around with Haskell on and off for a while, and am getting a "Stack space overflow" that I can't seem to correct.  I have a map containing about 2 million items.  Actually, it's a map keyed off of an Int where the element is another map keyed off of a string that has three Ints as its data.  The number of top level maps is pretty small (< 50), and the maps held by them hold a lot of entries.

I want to walk through all of the entries and gather some statistics, but I keep getting the stack overflow.  I worked down my test to an inner and outer fold that just counts the entries, and I still get the stack overflow.  I added 'seq' calls to make sure that the count isn't building up a bunch of undone operations, and I'm using foldlWithKey, and have also tried foldlWithKey' with the same result.

I get the count in my main function and immediately print it out.  Here is the relevant code:

outputIfNotFilteredCount1 :: Int -> KeyMap -> PuzzleMapRecord -> Int
outputIfNotFilteredCount1 inCount key entry
  = seq inCount (inCount + 1)

outputDatabaseCount1 :: Int -> Int -> InnerDB -> Int
outputDatabaseCount1 inCount smndCount innerDB
  = seq inCount (inCount + outCount)
  where
    outCount
      = Map.foldlWithKey' outputIfNotFilteredCount1 0 innerDB

main = do
...
    let
      count   = Map.foldlWithKey' outputDatabaseCount1 0 resultDB
    putStrLn $ "Database entries:" ++ (show count)


Any thoughts on why this is running out of stack space?

-Truman



Reply | Threaded
Open this post in threaded view
|

Stack overflow folding a map

Mateusz Kowalczyk
[1] might help you.

[1] - http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27

Mateusz K.

On 16/02/13 09:13, tcollin371 wrote:

> I've been playing around with Haskell on and off for a while, and am getting a "Stack space overflow" that I can't seem to correct.  I have a map containing about 2 million items.  Actually, it's a map keyed off of an Int where the element is another map keyed off of a string that has three Ints as its data.  The number of top level maps is pretty small (< 50), and the maps held by them hold a lot of entries.
>
> I want to walk through all of the entries and gather some statistics, but I keep getting the stack overflow.  I worked down my test to an inner and outer fold that just counts the entries, and I still get the stack overflow.  I added 'seq' calls to make sure that the count isn't building up a bunch of undone operations, and I'm using foldlWithKey, and have also tried foldlWithKey' with the same result.
>
> I get the count in my main function and immediately print it out.  Here is the relevant code:
>
> outputIfNotFilteredCount1 :: Int -> KeyMap -> PuzzleMapRecord -> Int
> outputIfNotFilteredCount1 inCount key entry
>   = seq inCount (inCount + 1)
>
> outputDatabaseCount1 :: Int -> Int -> InnerDB -> Int
> outputDatabaseCount1 inCount smndCount innerDB
>   = seq inCount (inCount + outCount)
>   where
>     outCount
>       = Map.foldlWithKey' outputIfNotFilteredCount1 0 innerDB
>
> main = do
> ...
>     let
>       count   = Map.foldlWithKey' outputDatabaseCount1 0 resultDB
>     putStrLn $ "Database entries:" ++ (show count)
>
>
> Any thoughts on why this is running out of stack space?
>
> -Truman
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>


Reply | Threaded
Open this post in threaded view
|

data, records and functions

Emanuel Koczwara
Hi,

I'm watching Philip Wadler "Faith, Evolution, and Programming
Languages" (very cool by the way):
http://www.youtube.com/watch?v=8frGknO8rIg

At 00:24:14 there is strange thing on the slide:

data Ord a = { less :: a -> a -> Bool }

It's first time I see function type (and where is definition?) in record
syntax. Can somebody explain this?

Emanuel




Reply | Threaded
Open this post in threaded view
|

data, records and functions

Darren Grant
This is just saying that the type of less is any function that takes two
a's as parameters and returns a Bool result. This appears to be a
formalization of the Ord (ordered) data type, where less would be used to
compare two ordered values and return a Bool result, either True or False.

Just a note that the data declaration above is missing a constructor name.
It should probably be something like:

data Ord a = *Ord* { less :: a -> a -> Bool }


Cheers,
Darren



On Wed, Feb 20, 2013 at 1:18 PM, Emanuel Koczwara <poczta at emanuelkoczwara.pl
> wrote:

> Hi,
>
> I'm watching Philip Wadler "Faith, Evolution, and Programming
> Languages" (very cool by the way):
> http://www.youtube.com/watch?v=8frGknO8rIg
>
> At 00:24:14 there is strange thing on the slide:
>
> data Ord a = { less :: a -> a -> Bool }
>
> It's first time I see function type (and where is definition?) in record
> syntax. Can somebody explain this?
>
> Emanuel
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130220/4824f6ed/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

data, records and functions

Peter Hall
In reply to this post by Emanuel Koczwara
> It's first time I see function type (and where is definition?) in record
> syntax. Can somebody explain this?

There's no definition, it's a parameter to the constructor, so the function
can be anything. Taking a much simpler example, you'll be familiar with, if
you do:

   data Foo a = Foo a

then the first argument to the Foo constructor also doesn't have a
definition. But when you use it to construct a value, then you provide one:

   myFoo = Foo 3

Likewise, when you construct an Ord value, you supply a function as the
value for the 'less' parameter:

   numOrd = Ord { less = (<) }

or you could use a different function for a different purpose:

   listLengthOrd = Ord { less = \ a b => length a < length b }



Hope that helps,

Peter


On 20 February 2013 21:18, Emanuel Koczwara <poczta at emanuelkoczwara.pl>wrote:

> Hi,
>
> I'm watching Philip Wadler "Faith, Evolution, and Programming
> Languages" (very cool by the way):
> http://www.youtube.com/watch?v=8frGknO8rIg
>
> At 00:24:14 there is strange thing on the slide:
>
> data Ord a = { less :: a -> a -> Bool }
>
> It's first time I see function type (and where is definition?) in record
> syntax. Can somebody explain this?
>
> Emanuel
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130221/ea512314/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

data, records and functions

Emanuel Koczwara
Hi,

Dnia 2013-02-21, czw o godzinie 02:48 +0000, Peter Hall pisze:

> > It's first time I see function type (and where is definition?) in
> record
> > syntax. Can somebody explain this?
>
>
> There's no definition, it's a parameter to the constructor, so the
> function can be anything. Taking a much simpler example, you'll be
> familiar with, if you do:
>
>
>    data Foo a = Foo a
>
>
> then the first argument to the Foo constructor also doesn't have a
> definition. But when you use it to construct a value, then you provide
> one:
>
>
>    myFoo = Foo 3
>
>
> Likewise, when you construct an Ord value, you supply a function as
> the value for the 'less' parameter:
>
>
>    numOrd = Ord { less = (<) }
>
>
> or you could use a different function for a different purpose:
>
>
>    listLengthOrd = Ord { less = \ a b => length a < length b }
>
>
>
>
>
>
> Hope that helps,
>
>
> Peter

  Thanks, it is clear now. I was missing that fields can be functions (a
field can hold a function).

-- here second field is a function
data Command a = Command a (a -> a)

-- do something "useful" with that
executeCommand :: Command a -> a
executeCommand (Command param function) = function param

-- test
executeCommand (Command 5 succ) == 6

  Thank you, it was so simple :)

Emanuel