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)
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.