I have a question relating to the use of Data.Map.  I admit I havn't
fully understood all the concepts of functional programming yet, and
thus am having trouble understanding how one might employ the Data.Map type.

Consider the following python code:

===============
combos = dict()

def get_num_combos(n,r):
   if (n,r) not in combos:
     if r is 1:
       combos[(n,r)] = n
     else:
       combos[(n,r)] = sum(get_num_combos(x,r-1) for x in xrange(r-1,n))
   return combos[(n,r)]
===============

get_num_combos() returns the number of ways to select r items from a set
of n objects (I know there are more efficient ways to do this, but that
is not the point of this post).

I've had no trouble implementing the get_num_combos function in haskell
- very straight forward and simple... however, I cannot seem to find a
way to use Data.Map in place of python's dict().  The problem with that
is, without some form of caching, get_num_combos can take a very long
time to return the solution for certain inputs.  I'm not concerned about
long term caching of results, more that a Data.Map is used to cache
results and prevent the same calculation being performed more than once.

I'd also like to state ahead of time that this is not a homework
question... I know it sounds like one.  In fact it's inspired by problem
53 on projecteuler.net, which I was able to solve using the python
function above.  I'm now just curious as to how one might implement this
same algorithm in haskell

Thanks in advance.

Regards,

I'll use,

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

If I follow your code somewhat slavishly, and pull out a state monad to
express the sequencing of cache queries,

getNumCombos n r =
    evalState (useCacheFor n r) Map.empty
    where
      useCacheFor n 1 = return n
      useCacheFor n r =
          do cache <- get
             case Map.lookup (n, r) cache of
               Nothing -> do results <- sequence [ useCacheFor x (r-1)
                                                   | x <- [ r-1 .. n-1 ] ]
                             let result = sum results
                             put (Map.insert (n, r) result cache)
                             return result
               Just result -> return result

probably works fairly similarly to your code. There'll no doubt be some
laziness issues that others can comment on.

Or, a shorter version that exploits lazy evaluation instead of being
quite so stateful is,

getNumCombos n' r' =
  let cache = Map.fromList [ ((n, r), useCacheFor n r) | n <- [ 1 .. n'],
                                                         r <- [ 1 .. n ] ]
      useCacheFor n 1 = n
      useCacheFor n r = sum [ cache ! (x, r-1) | x <- [ r-1 .. n-1 ] ]
  in cache ! (n', r')

(I didn't think too hard about the domain that cache needs.)

I look forward to seeing others' criticisms of these. (-: Especially, I
can never remember much about what's done idiomatically for this sort of
problem.

You could have the cache live outside the function and be passed into
it, of course; indeed, even outside it could live inside some kind of
state monad. You don't usually get to have an updatable variable without
using /some/ kind of monad, though - for instance, IORefs live in the IO
monad.

I hope I've helped more than I've confused. I can certainly explain any
of the above code if any of it seems mysterious.

Recipe: Start with the recursive function. The paramter r is
traditionally called k, and it's also traditional to use k=0 as base
case instead of k=1:

  combos (n,0) = 1
  combos (n,k) = sum [combos (x,k-1) | x <- [k-1..n-1]]

Let's test that:

  test f = [[f (n,k) | k <- [0..n]] | n <- [0..5]]

*Main> test combos
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]

Now, the trick. Store everything in an array of size maxCombos:

  maxCombos = 10

  comboArray = array ((0,0),(maxCombos, maxCombos)) comboVals

The function now just accesses the array:

  combos nk = comboArray ! nk

Rename the original function combos from above to combo', but
leave the name for the recursive call(s) alone, so instead it will
now read the values from the array:

  combos' (n,0) = 1
  combos' (n,k) = sum [combos (x,k-1) | x <- [k-1..n-1]]

And the values used to initialize the array are just calls to combos':

  comboVals = [((n,k),combos' (n,k)) | n <- [0..maxCombos], k <- [0..n]]

That's it. Test:
*Main> test combos
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]

Still works :-) It looks completely circular if you're used to imperative
programming, but it works because the values stored in the array are
not actually evaluated until you access them. Also note that we have
left one half of the array undefined, if you try to access this part,
you'll get an error:

*Main> combos (2,3)
*** Exception: (Array.!): undefined array element

You can do the same with Data.Map instead of an array (exercise :-).
Which one do you think needs more memory?

See also <20071116074410.C3E.1.NOF...@dthierbach.news.arcor.de> (or

http://groups.google.com/group/comp.lang.haskell/browse_thread/thread...

if your newsserver doesn't have it) for a way to do memoization that
doesn't require using toplevel declarations everywhere. That also
explains the connection between memoization and fixpoints ("functional
recursion", if you want).

  combos (n,k) = combos (n-1,k) + combos (n-1,k-1)

For the problem, we need all combos up to some n anyway (the complete
Pascal's triangle), so we turn this recursion inside out and *generate*
the whole line for n from the line for (n-1). Then we iterate this process,
which yields an infite list.

  next l = zipWith (+) (0 : l) (l ++ [0])

  pascal = iterate next [1]

Example usage:

*Main> next [1,3,3,1]
[1,4,6,4,1]
*Main> take 5 pascal
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Exercise: Use "filter" and "concat" to write an additional one-line-function
that solves problem 53 :-).