1

I'm a Haskell novice trying to solve a problem about the length of Collatz sequences for different numbers. I was hoping to write a function using memoization, but I got stuck:

-- map for memoization
collLength:: Data.Map.Map Int Int
collLength = Data.Map.fromList [(1,0)]

-- collatz n returns the length of the sequence starting in n
collatz:: Int -> Int
collatz n =
    case (Data.Map.lookup n collLength) of
        Just x -> x
        Nothing ->
            let result
                | n `mod` 2 == 0    = 1 + collatz (n `div` 2)
                | otherwise         = 1 + collatz (3*n + 1)
            in do
                Data.Map.insert n result collLength
                return result 

I want to fill the map with newly calculated results. However, I get the following error:

Couldn't match type 'Data.Map.Map Int Int' with 'Int'

Expected type: Data.Map.Map Int Int -> Data.Map.Map Int Int -> Int

Actual type: Data.Map.Map Int Int -> Data.Map.Map Int Int -> Data.Map.Map Int Int

from the final block. How can I insert the new value and then have the collatz function return it?

2 Answers 2

3

To add to bhelkir's excellent answer, the usual way to do memoization in Haskell is to define a data structure (usually a trie) that associates argument values with their results. If there are infinitely many possible argument values, this will be an infinitely large data structure, but thanks to lazy evaluation, such structures are doable in Haskell.

The fibs example that he gives is one such data structure—each Fibonacci number is associated with its corresponding argument value by appearing at the corresponding index of an infinite list. But it's generally better to use some sort of search tree representation in order to get O(log(n)) search times. This SO entry goes into more depth about this.

There are also libraries that provide generic memoization:

2

You can't. The value collLength is immutable, it can't be modified after it's defined. In order to have "state" you must use a monad that supports it, or you can use laziness in some cases to act like memoization (see footnote). In this case, the easiest you could do this is probably by using the State monad from the mtl library:

import Control.Monad.State
import Data.Map (Map)
import qualified Data.Map as M

-- "State s a" means that "s" is the stateful value
-- and "a" is the return value of a monadic operation
collatz :: Integer -> State (Map Integer Integer) Integer
collatz n = do
    -- Get the current memoization map
    collLength <- get
    -- look up the current n as before
    case M.lookup n collLength of
        Just x -> return x
        Nothing -> do
            -- Calculate either collatz (n `div` 2) or collatz (3 * n + 1)
            -- and increment the result by 1
            result <- fmap (1+) $
                if even n
                    then collatz (n `div` 2)
                    else collatz (3 * n + 1)
            -- Modify the current memoization map to include our new result
            modify (M.insert n result)
            return result

evalCollatz :: Integer -> Integer
evalCollatz n = evalState (collatz n) $ M.singleton 1 0

Then this can be run using evalState or runState. The former will just return the collatz length, while the latter will return a tuple containing the length and the memoized map. Notice that I've changed from using Int to Integer to allow for arbitrarily large values as well.

An example usage would be

> evalCollatz 100
25
> evalCollatz 4029438019378410983794857103401801934908745019384013795092745080123949028750238401290701092387401894671234110985710984671039485712039584
3269

On my computer this executes pretty much immediately (:set +s says that it took 0.03 seconds, but this isn't an accurate profiling technique).

If you are wanting to calculate the collatz length for a range of numbers, then you can use the monadic combinator mapM:

> maximum $ evalState (mapM collatz [1..100000]) $ M.singleton 1 0
350

This will preserve the state between calls to collatz.

Footnote:

For some cases laziness can be more easily exploited to avoid solutions like the state monad. The most common example would be for generating the entire fibonacci sequence:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

This recursive definition will build an infinite lazy list of all the fibonacci numbers with "memoization", in that it uses the results of previous values to calculate the next value.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.