Basic Haskell Functions

Question

I am new to Haskell and I am trying to learn the basics. I need to declare a type called Pos for position that will have two integers and then I need to have the Directions North,South,West, East so that I can alter the position based on the direction. Once I do that I need to make a function called moves that will take a list of moves and the initial position and return the position after all the moves. Here is my code but I am stuck at the point that I have to iterate through the list of moves.

type Pos = (Int, Int)
data Direction = North | South | East | West

move :: Direction -> Pos -> Pos
move North (x,y) = (x, y+1)
move West (x,y) = (x-1, y)
move South (x,y) = (x, y-1)
move East (x,y) = (x+1, y)

moves :: [Direction] -> Pos -> Pos
moves [] (x,y) = (x,y)
moves (h:xs) (x,y) 
        | h == North = move North (x,y)
        | h == West  = move West (x,y)
        | h == South = move South (x,y)
        | otherwise  = move East (x,y)

What am I missing here?

Answer 1

Combining a list of things into one thing is called folding the list. There are (approximately) two list folds: foldl and foldr. Leaning to use folds is an important step in learning Haskell. We need foldl, which has type

foldl :: (a -> b -> a) -> a -> [b] -> a

Now foldl works by using a combining function and an initial value to combine the stuff in a list, so for example

foldl (£) s [x,y,z] = (((s £ x) £ y) £ z)

(The l in foldl is short for left, so it's there to help you remember that your starting value s will end up at the left but more importantly that the brackets are associated to the left.)

The third argument is a list argument [b]. We'll use that for the list of moves, so the type b will be Direction.

The second argument is a starting value of type a, so we'll use that for your initial position, so type a will be Pos.

The first argument is a function to combine something from your list with a current value. Now that we know the types b and a are Direction and Pos we know that our combining function must have type Pos -> Direction -> Pos. The move function is almost exactly what we need, except we need to swap the arguments. The flip function does that, so flip move has the type we need.

So we'll specialise the type of foldl to be

foldl :: (Pos -> Direction -> Pos) -> Pos -> [Direction] -> Pos

and define

moves :: [Direction] -> Pos -> Pos
moves ds i = foldl (flip move) i ds

---

Now foldl has a "strict" version called foldl' which in this case is faster, so if you were using it in a fast-paced game, or were handling a very large number of moves, you'd want to use that one.

As always, you can find functions by searching for their name or type on hoogle.

There's also a foldr function which folds a list a different way. You can read about the difference between them in this question. In short, though, foldr works like this:

foldr (?) s [x,y,z] = (x ? (y ? (z ? s)))

(The r in foldr is short for right, so it's there to help you remember that your starting value s will end up at the right but more importantly that the brackets are associated to the right.)

Answer 2

Either before or after the single move corresponding to h, you need to make a recursive call to moves for the rest of the Directions. If before, then each case becomes something like:

move North (moves xs (x,y))

if you want it to be after, which is probably the right approach given the problem specification, then it would be:

moves xs (move North (x,y))

However repeating the case analysis in moves is a bit unnecessary as you can just call move directly with h, e.g.

moves (h:xs) (x,y) = moves xs (move h (x,y))

In fact you don't even need to explicitly pattern-match on the (x,y) tuple;

moves (h:xs) pos = moves xs (move h pos)

As another answer points out, this is the same as the built-in foldl function (up to the arguments order), but it's probably best to understand how to do it by hand first.