CODEWITHSUNDEEP
haskell
philomathic_life
philomathic_life

Reputation: 514

ZipWith without evaluating elements more than once in Haskell

I have an infinite list, dog (not the actual name) whose elements are generated by a somewhat-slow function, so I'm trying to avoid having to generate the same element more than once. The problem is I want the following new list, cat:

let cat = zipWith (++) dog $ tail dog

Am I correct in believing that cat is created by evaluating each element of dog twice (from dog and tail dog) then concatenating the two elements? If so, is there a way that I can get Haskell to "realize" that the elements of dog are precisely the same as tail dog just shifted one to the left so that I can "pass the value" of the previous element of tail dog to the current element of dog? That is to say, since I know that the i-th element of dog is equal to the (i - 1) element of tail dog, I want my program to just re-use the (i - 1) element of tail dog instead of recalculating it.

I know lists like the canonical creation of the Fibonacci sequence, let fib = 0:1:zipWith (+) fib $ tail fib only evaluate the elements once; but that is because the list is defined on itself while cat is not.

I apologize if this is a dumb question, but my brain hasn't been firing on all cylinders lately. If knowing the specific list in question will be useful, then I'll be more than happy to provide it. Thanks.

Upvotes: 1

Views: 329

Answers (2)

jamshidh
jamshidh

Reputation: 12060

@sepp2k is correct, but at the same time, sometimes it is useful to be able to verify these things directly.... (here is was obvious, but in slightly more complicated cases, it isn't as clear).

You can always watch the program in action by using the (unsafe) trace function, like this....

import Debug.Trace

main :: IO ()
main = do
  let dog = listFrom 0
      cat = zipWith (++) dog $ tail dog

  print $ take 10 cat

listFrom::Int->[String]
listFrom x = trace ("in listFrom: " ++ show x) $ 
    show x:listFrom (x+1)

This will show you how many times each element was calculated (followed by the output of the program)....

in listFrom: 0
in listFrom: 1
in listFrom: 2
in listFrom: 3
in listFrom: 4
in listFrom: 5
in listFrom: 6
in listFrom: 7
in listFrom: 8
in listFrom: 9
in listFrom: 10
["01","12","23","34","45","56","67","78","89","910"]

As expected, it creates each item only once.... More interestingly, you can see that (because of laziness), no item in the list is created if you don't use the created list.... For instance, change

print $ take 10 cat

to

putStrLn "Not using cat"

and nothing gets printed out

> runProgram
Not using cat

(Just remember, though, trace is unsafe and should never be used in the final program, it is only intended for debugging)

Upvotes: 1

sepp2k
sepp2k

Reputation: 370112

Am I correct in believing that cat is created by evaluating each element of dog twice

No, each element of a list (or more generally: each variable and each element of a algebraic data type or record) will be evaluated at most once.

I know lists like the canonical creation of the Fibonacci sequence [...] only evaluate the elements once; but that is because the list is defined on itself while cat is not.

No, that's not why. It's because a lazy list is not the same thing as the concept of a generator you might know from other languages. A lazy list is an actual data structure that exists (partly) in memory once it's been (partly) evaluated.

That is, after you've used, say, the first ten elements of the list, those elements will actually exist in memory and any subsequent usage of those elements will simply read them from memory rather than calculating them again.

Upvotes: 3

Related Questions