Stack overflow folding a map
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
[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@haskell.org http://www.haskell.org/mailman/listinfo/beginners
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
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 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@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
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
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@haskell.org http://www.haskell.org/mailman/listinfo/beginners
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
participants (5)
-
Darren Grant -
Emanuel Koczwara -
Mateusz Kowalczyk -
Peter Hall -
tcollin371