Data.Tree.unfoldTree evaluates more than once for the same input

Question

I have to generate a tree whose branches represent various sequences of choices. I have three rows (front, middle and back) and a set number of items that can enter each row. Each node in the tree represents an order for items to enter. I am using Data.Tree.unfoldTree as follows:

import Data.Tree as Tree
import Data.Seq as Seq

data RowType = Front | Middle | Back
data ChoiceTreeBuildLabel = Label (Seq.Seq RowType) Int Int Int

choiceTreeBuilder :: ChoiceTreeBuildLabel -> 
                     (Seq.Seq RowType, [ChoiceTreeBuildLabel])
choiceTreeBuilder (Label rt f m b) = (rt, concat [ff,mf,bf])
    where
        ff = if f == 0 then [] else [Label (Front <| rt) (f-1) m b]
        mf = if m == 0 then [] else [Label (Middle <| rt) f (m-1) b]
        bf = if b == 0 then [] else [Label (Back <| rt) f m (b-1)]

choiceTree f m b = Tree.unfoldTree choiceTreeBuilder (Label Seq.empty f m b)

However, when for example evaluating length . last . Tree.levels $ choiceTree 3 4 5, it does not seem that the value of this function is stored. That is, the function seems to need to generate a new tree, regardless of whether the function has already been evaluated. I may be wrong, but I was under the impression that Haskell should only need to compute this one time, and indeed that is what I had intended. Can someone help me out?

Here's relevant question: http://stackoverflow.com/questions/5749039/automatic-memoizing-in-functional-programming-languages — fizruk, May 19 '14 at 10:09

score 0 · Answer 1 · answered Mar 26 '15 at 15:18

Haskell does not memoize function application in general! Otherwise, imagine how much memory the runtime would use as any application of anything got memoized. Not to mention which, how would it even "know" that you were calling with the "same" value if you did not provide some appropriate notion of "sameness" yourself.

You can "purely" memoize a function either by hand, or with an appropriate helper package. Two common ones people tend to use are MemoTrie (http://hackage.haskell.org/package/MemoTrie) and memocombinators (http://hackage.haskell.org/package/data-memocombinators)

A more complex but similar notion is provided by the Representable Trie library (http://hackage.haskell.org/package/representable-tries-3.0.2/docs/Data-Functor-Representable-Trie.html)

Data.Tree.unfoldTree evaluates more than once for the same input

1 Answers1