A tricky haskell problem

Question

I had this task for my Haskell class, but I find it quite difficult. If you could help a bit. You are given a maze

maze = ["x xxx",
        "x   x",
        "x x x",
        "x x  ",
        "xxxxx"]

and you can walk through spaces only . You start from (0,1) and the function have to return a string with directions to escape the maze which are :

f - forward
r- turn right
l - turn left 

And if you have a choice you always prefer right to forward, and forward to left. For the current example the answer is ffllffrffrfflf

Thanks in advance

data Direction = N | W | S | E deriving (Show,Eq)

maze = ["x xxx",
        "x   x",
        "x x x",
        "x x  ",
        "xxxxx"]

d = 's'
pos = (0,1)

fpath d pos | fst pos == (length maze - 1) = ""
            | snd  (pos) ==0 || (snd ( pos ) == ((length (maze!!0))-1)) = ""
            | rightPossible d pos = "r" ++ ( fpath (rightRotate d) pos )
            | forwardPossible d  pos = "f" ++ ( fpath d (nstep d pos) )
            | True = "l" ++ fpath (leftRotate d) pos
            where nstep :: Direction -> (Int, Int) -> (Int, Int) {-next step-}
                  nstep N (x,y) = (x-1,y)
                  nstep W  (x,y) = (x,y-1) 
                  nstep S (x,y) = (x+1,y) 
                  nstep E  (x,y) = (x,y+1)

                  rightPossible :: Direction -> (Int, Int) -> Bool 
                  rightPossible N (x,y)= (maze !! x)!! (y+1) == ' '
                  rightPossible W (x,y)= (maze !! (x-1))!! y   == ' '              
                  rightPossible S (x,y)= (maze !! x)!! (y-1) == ' '                   
                  rightPossible E (x,y)= (maze !! (x+1))!! y   == ' '

                  rightRotate :: Direction -> Direction 
                  rightRotate N = E
                  rightRotate W = N
                  rightRotate S = W
                  rightRotate E = S

                  forwardPossible :: Direction -> (Int, Int) -> Bool 
                  forwardPossible N (x,y)= ((maze !! (x-1))!! y) == ' ' 
                  forwardPossible W (x,y)= ((maze !! x)!! (y-1)) == ' '
                  forwardPossible S (x,y)= ((maze !! (x+1))!! y) == ' '
                  forwardPossible E (x,y)= ((maze !! x)!! (y+1)) == ' '

                  leftRotate :: Direction -> Direction
                  leftRotate N = W
                  leftRotate W = S
                  leftRotate S = E
                  leftRotate E = N

Answer 1

I agree with FUZxxl. If you make a new data type, you can do stuff like

Data types

data Direction = North | West | South | East deriving (Show,Eq) 
type Point = (Int, Int)

Using the data types in a readable and efficient way

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

Again here. Also, using well-named functions instead of just r, which doesn't mean much.

rightPossible :: Direction -> Point -> Bool
rightPossible North = (maze !! x)!! (y-1) == ' '
rightPossible West  = (maze !! x+1)!! y   == ' '              
rightPossible South = (maze !! x)!! (y+1) == ' '                   
rightPossible East  = (maze !! x-1)!! y   == ' '

Hope this helps you understand the language a little.

edit: changed data Point to type Point

Answer 2

The first thing I see is, that you have a precedence issue. The expression (maze !! x)!! y-1 is parsed as ((maze !! x)!! y)-1 whereas you want it parsed as (maze !! x)!! (y-1). Add braces to solve this issue.

After adding this, your code compiles, although your algorithm seems to be broken. Maybe somebody else can help you.

Some coding advises:

• Add type signatures at appropriate places to ease debugging. (If the type fails, the compiler will more likely show the error in the right place)

• Use pattern matching instead of extra case statements. Instead of

  nstep d (x,y)   {-next step-}
                  | d == 'n' = (x-1,y)
                  | d == 'w' = (x,y-1)
                  | d == 's' = (x+1,y)
                  | d == 'e' = (x,y+1)
  

  write

  nstep 'n' (x,y) = (x-1,y)
  nstep 'w' (x,y) = (x,y-1)
  nstep 's' (x,y) = (x+1,y)
  nstep 'e' (x,y) = (x,y+1)
  

• Write your own data types instead of relying on characters. For instance, you could create an own datatype for directions:

  data Direction = N | W | S | E deriving (Show,Eq)