Haskell question about memoization / evalution

I am trying to write a "how to make amount with access to coins to denominations coins, using the fewest coins" function in Haskell. I implemented this with DFS, which works but is quickly too slow. In Python (my main language) I can memoize the results and have the same algorithm run very quickly. I attempted to do the same thing in Haskell, with minimal success.

I will give a toy version of the problem where I am trying to understand memoization, and then show the DFS that I am actually trying to memoize.

Toy problem

From Haskell Wiki's page on memoization, one way of doing this is to index into an infinite list. A similar gist.

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

This makes sense to me -- the regular recursive relation calls the index of the memoized list, which gives the value if it has it and can fall back to the helper function. :thumbsup:

A minor modification breaks this:

memoized_fib :: Int -> Integer
memoized_fib n = (map fib [0 ..] !! n)  -- now no longer lazily evaled!
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

-- these are not lazily eval'ed either
-- memoized_fib n = (map fib [0 ..] !! ) n
-- memoized_fib  = (\n -> map fib [0 ..] !! n)

If I just wanted to implement the Fibonannci sequence, I could take !! has to be left partial as a rule of life and ignore it. I am trying to get a better understanding of this, because my function has a recursion on only one argument, and having !! "point-free" is challenging.

My non-memoized version

This is the non-memoized code I wrote, which hopefully is self-explanatory:

import Data.List

smallestMaybeList :: Maybe [Integer] -> Maybe[Integer] -> Maybe[Integer]
smallestMaybeList (Just a) Nothing = (Just a)
smallestMaybeList Nothing (Just b) = (Just b)
smallestMaybeList Nothing Nothing = Nothing
smallestMaybeList (Just a) (Just b) = if (length a) < (length b) then (Just a) else (Just b)


makeChange :: Integer -> [Integer] -> Maybe [Integer]
makeChange 0 _ = Just []
makeChange _ [] = Nothing
makeChange amount coins
  | amount < 0 = Nothing
  | amount `elem` coins = Just [amount]
  | otherwise = foldl' smallestMaybeList Nothing [(++) [c] <$> makeChange (amount-c) remCoin | c <- remCoin]
      where remCoin = [c | c <- coins, c < amount]

For my (attempt) at a memoized version, I gave up on recursing on the coins to only use denominations not bigger than the current amount, and have this (which is still eagerly evaluated)

import Data.List

--smallestMaybeList :: Maybe [Integer] -> Maybe[Integer] -> Maybe[Integer]
smallestMaybeList (Just a) Nothing = (Just a)
smallestMaybeList Nothing (Just b) = (Just b)
smallestMaybeList Nothing Nothing = Nothing
smallestMaybeList (Just a) (Just b) = if (length a) < (length b) then (Just a) else (Just b)

makeChange :: Integer -> [Integer] -> Maybe [Integer]
makeChange 0 coins = Just []
makeChange amount coins
  | amount < 0 = Nothing
  | otherwise = [mch a coins | a <- [0..]] !! (fromInteger amount)

-- this is "make change helper"
mch :: Integer -> [Integer] -> Maybe [Integer]
mch 0 _ = Just []
mch _ [] = Nothing
mch amount coins
  | amount < 0 = Nothing
  | amount `elem` coins = Just [amount]
  | otherwise = foldl' smallestMaybeList Nothing [(++) [c] <$> makeChange (amount-c) coins | c <- coins]

I have tried other variations where the helper function was inline / nested, and it did not make much difference.

The idea of indexing into an infinite list for fib seemed so much more generalizable than the zipWith infinite list trick, but even on a toy problem I am getting stuck pretty much immediately.

Questions:

Why does translating from point-free to named variables change from lazy to eager evaluation?
Advice on how to memoize my current algo?

Solution

Why does translating from point-free to named variables change from lazy to eager evaluation?

It's not about making the program pointfree, but about defining the memoization list outside of the function. It's the difference between creating an list once for all, and having every recursive call create a new list and thus not reuse work from previous calls.

Concretely, for Fibonacci, the operator section desugars to

mamoized_fib = let fiblist = map fib [0..] in \n -> fiblist !! n

where the list fiblist is defined outside of the lambda, so it exists before any argument is provided. If you instead wrote

fib n = map fib [0..] !! n

then the list is defined inside of the lambda, so the list is only accessible when the function is applied, so every recursive call generates its own new list.

The goal is to memoize a recursive function of type Int -> a for some a, assuming the Ints are positive (the argument could be something else, you'd have to use a different data structure than lists). So first you have to rewrite your code to make the recursive function have that type. In particular, you should turn the list of coins into a "global" parameter instead of carrying it around at every recursive call. The actual recursive function can then be defined locally in a let or where clause.

import Data.Function
import Data.Foldable

makeChange :: [Int] -> Int -> [Int]
makeChange coins = make
  where
    make :: Int -> [Int]
    make 0 = []
    make amount = minimumBy (compare `on` sum) [ c : make (amount - c) | c <- coins, c <= amount ]

We want to memoize make. Once you have written it as a function Int -> [Int], the process is very straightforward.

Put the results in a list
```
 makeList = make <$> [0..]
```
Define (what will be) the memoized function by indexing into the list
```
 memoMake :: Int -> [Int]
 memoMake n = makeList !! n
```
Note again that it doesn't matter whether you use an operator section ((makeList !!)) or not (\n -> makeList !! n), just that the list is defined outside of the scope of the index n. (It's only after you inline makeList that the operator section makes a difference.)
Where make was called previously (i.e., everywhere except in makeList) change calls to make into calls to memoMake. Here there are two occurrences (one in the body of makeChange, one in the body of make).

import Data.Function
import Data.Foldable

makeChange :: [Int] -> Int -> [Int]
makeChange coins = memoMake
  where
    make :: Int -> [Int]
    make 0 = []
    make amount = minimumBy (compare `on` sum) [ c : memoMake (amount - c) | c <- coins, c <= amount ]
    makeList :: [[Int]]
    makeList = make <$> [0 ..]
    memoMake :: Int -> [Int]
    memoMake n = makeList !! n