CODEWITHSUNDEEP
haskell
ElectricHedgehog
ElectricHedgehog

Reputation: 173

Performance of a function that changes functions

Lets suppose we have a function

type Func = Bool -> SophisticatedData
fun1 :: Func

And we'd like to change this function some input:

change :: SophisticatedData -> Func -> Func
change data func = \input -> if input == False then data else func input

Am I right that after several calls of change (endFunc = change data1 $ change data2 $ startFunc) resulting function would call all intermediate ones each time? Am I right that GC wouldn't able to delete unused data? What is the haskell way to cope with this task?

Thanks.

Upvotes: 0

Views: 170

Answers (2)

Daniel Wagner
Daniel Wagner

Reputation: 152682

You are correct: if foo is a chain of O(n) calls to change, there will be O(n) overhead on every call to foo. The way to deal with this is to memoize foo:

memoize :: Func -> Func
memoize f = \x -> if x then fTrue else fFalse where
    fTrue  = f True
    fFalse = f False

Upvotes: 1

daniel gratzer
daniel gratzer

Reputation: 53871

Well let's start by cleaning up change to be a bit more legible

change sd f input = if input then func input else sd

So when we compose these

change d1 $ change d2 $ change d3

GHC starts by storing a thunk for each of them. Remember that $ is a function to so the whole change d* thing is going to be a thunk at first. Thunks are relatively cheap and if you're not creating 10k or so of them at once you'll be just fine :) so no worries there.

Now the question is, what happens when you start evaluating, the answer is, it'll still not evaluate the complex data, so it's still quite memory efficient, and it only needs to force input to determine which branch it's taking. Because of this, you should never actually fully evaluate SophisticatedData until after choose has run and returned a one to you, then it will be evaluated as need if you use it.

Further more, at each step, GHC can garbage collect the unneeded thunks since they can't be referenced anymore.

In conclusion, you should be just fine. Trust in the laziness

Upvotes: 3

Related Questions