Project Euler #15 in haskell

Question

I've solved Project Euler #15 in Haskell, but I feel like there might be a better way to express my solution that I'm not seeing. I start out defining my types:

import qualified Data.Map.Strict as Map
import Data.List

data Position = Position Int Int
                deriving (Show, Eq, Ord)

start :: Position
start = Position 20 20

I probably should have used newtype on a tuple of Ints, but I think this is ok. I can then generate the list of moves available from a given position via:

moves :: Position -> [Position]
moves (Position x y) | x == 0 && y == 0 = []
                     | x == 0 = [Position x (y - 1)]
                     | y == 0 = [Position (x - 1) y]
                     | otherwise = Position (x - 1) y : Position x (y - 1) : []

From there a naive implementation to solve for the number of paths would simply look like:

naiveWays :: Position -> Int
naiveWays (Position 0 0) = 1
naiveWays pos = sum $ map naiveWays $ moves pos

Of course this is highly inefficient, and takes much to long to complete, so I tried to improve it using memoization. This is where I feel like I could probably use the most improvement:

ways :: Position -> Int
ways = snd . memWays Map.empty

memWays :: Map.Map Position Int -> Position -> (Map.Map Position Int, Int)
memWays mem (Position 0 0) = (mem, 1)
memWays mem pos = loop lookupWays
  where
    lookupWays = Map.lookup pos mem
    computeWays = mapAccumR memWays mem (moves pos)
    mapWays = fst computeWays
    sumWays = sum $ snd computeWays
    loop (Just w) = (mem, w)
    loop (Nothing) = (Map.insert pos sumWays mapWays, sumWays)

Basically memWays takes a Map of known solutions for the subproblems (number of paths from 2,2, etc), and a position and attempts to use it to find the shortest path. If the position is already in the map, it can simply look it up. Otherwise, it maps over the available moves, using the returned Map as an accumulator.

There actually is an even more efficient way to solve it, but I won't spoil that, and since I'm looking for Haskell practice, not math, I'm more interested in figuring out how I can make this approach cleaner.

Edit: Thanks to 200_success for pointing out that I don't need to enumerate moves. memWays now looks like:

memWays :: Map.Map Position Int -> Position -> (Map.Map Position Int, Int)
memWays mem (Position 0 _) = (mem, 1)
memWays mem (Position _ 0) = (mem, 1)
memWays mem pos@(Position x y) = loop $ Map.lookup pos mem
  where right = memWays mem $ Position (x - 1) y
        down = memWays (fst right) $ Position x (y - 1)
        both = snd right + snd down
        loop (Just paths) = (mem, paths)
        loop Nothing = (Map.insert pos both $ fst down, both)

I feel like this looks a lot cleaner, though if anyone has suggestions for further improvement, I'd love to hear it.

Answer 1

There's no need to list all the moves. Here is an unmemoized solution:

naiveWays :: Position -> Int
naiveWays (Position 0 _) = 1
naiveWays (Position _ 0) = 1
naiveWays (Position x y) = (naiveWays (Position (x - 1) y)) +
                           (naiveWays (Position x (y - 1)))

Note that it also takes better advantage of pattern matching.