Coordinates for clockwise outwards spiral

Question

I'm trying to make what I think is called an Ulam spiral using Haskell. It needs to go outwards in a clockwise rotation:

   6 - 7 - 8 - 9
   |           |
   5   0 - 1   10
   |       |   |
   4 - 3 - 2   11
               |
 ..15- 14- 13- 12

For each step I'm trying to create coordinates, the function would be given a number and return spiral coordinates to the length of input number eg:

mkSpiral 9
> [(0,0),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1),(1,1)]

(-1, 1) - (0, 1) - (1, 1)
   |        
(-1, 0)   (0, 0) - (1, 0)
   |                 |
(-1,-1) - (0,-1) - (1,-1)

I've seen Looping in a spiral solution, but this goes counter-clockwise and it's inputs need to the size of the matrix.

I also found this code which does what I need but it seems to go counterclock-wise, stepping up rather than stepping right then clockwise :(

type Spiral = Int
type Coordinate = (Int, Int)

-- number of squares on each side of the spiral
sideSquares :: Spiral -> Int
sideSquares sp = (sp * 2) - 1

-- the coordinates for all squares in the given spiral
coordinatesForSpiral :: Spiral -> [Coordinate]
coordinatesForSpiral 1 = [(0, 0)]
coordinatesForSpiral sp = [(0, 0)] ++ right ++ top ++ left ++ bottom
  where fixed = sp - 1
        sides = sideSquares sp - 1
        right = [(x, y) | x <- [fixed], y <- take sides [-1*(fixed-1)..]]
        top = [(x, y) | x <- reverse (take sides [-1*fixed..]), y <- [fixed]]
        left = [(x, y) | x <- [-1*fixed], y <- reverse(take sides [-1*fixed..])]
        bottom = [(x, y) | x <- take sides [-1*fixed+1..], y <- [-1*fixed]]

-- an endless list of coordinates (the complete spiral)
mkSpiral :: Int -> [Coordinate]
mkSpiral x = take x endlessSpiral

endlessSpiral :: [Coordinate]
endlessSpiral = endlessSpiral' 1

endlessSpiral' start = coordinatesForSpiral start ++ endlessSpiral' (start + 1)

After much experimentation I can't seem to change the rotation or starting step direction, could someone point me in the right way or a solution that doesn't use list comprehension as I find them tricky to decode?

Answer 1

Let us first take a look at how the directions of a spiral are looking:

R D L L U U R R R D D D L L L L U U U U ....

We can split this in sequences like:

      n times       n+1 times
       _^_           __^__
      /   \         /     \
R … R D … D L L … L U U … U
\_ _/       \__ __/
  v            v
n times     n+1 times

We can repeat that, each time incrementing n by two, like:

data Dir = R | D | L | U

spiralSeq :: Int -> [Dir]
spiralSeq n = rn R ++ rn D ++ rn1 L ++ rn1 U
    where rn = replicate n
          rn1 = replicate (n + 1)

spiral :: [Dir]
spiral = concatMap spiralSeq [1, 3..]

Now we can use Dir here to calculate the next coordinate, like:

move :: (Int, Int) -> Dir -> (Int, Int)
move (x, y) = go
    where go R = (x+1, y)
          go D = (x, y-1)
          go L = (x-1, y)
          go U = (x, y+1)

We can use scanl :: (a -> b -> a) -> a -> [b] -> [a] to generate the points, like:

spiralPos :: [(Int, Int)]
spiralPos = scanl move (0,0) spiral

This will yield an infinite list of coordinates for the clockwise spiral. We can use take :: Int -> [a] -> [a] to take the first k items:

Prelude> take 9 spiralPos
[(0,0),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1),(1,1)]