Координаты спирали, направленной наружу по часовой стрелке.

Идея следующего решения состоит в том, что вместо того, чтобы пытаться напрямую сгенерировать координаты, мы будем смотреть на направления от одной точки к другой. Если вы сделаете это, вы заметите, что, начиная с первой точки, мы идем 1 × вправо, 1 × вниз, 2 × влево, 2 × вверх, 3 × вправо, 3 × вниз, 4 × влево ... Затем они могут быть разделены на направление и количество повторений:

direction: > v < ^ > v < …
   # reps: 1 1 2 2 3 3 4 …

И это на самом деле дает нам два действительно простых шаблона! Направления просто меняются >, v, <, ^, >, в то время как количество повторений увеличивается на 1 каждые 2 раза. После того, как мы составили два бесконечных списка с этими шаблонами, их можно объединить вместе, чтобы получить общий список направлений >v<<^^>>>vvv<<<<…, который затем можно повторять для получения значений координат.

Я всегда думал, что просто дать кому-то кучу кода в качестве решения - не лучший способ обучения, поэтому я настоятельно рекомендую вам попробовать реализовать вышеупомянутую идею самостоятельно, прежде чем смотреть на мои решение ниже.

С возвращением (если вы все же пытались реализовать это самостоятельно). Теперь: к моему собственному решению. Сначала я определяю тип данных Stream для бесконечного потока:

data Stream a = Stream a (Stream a) deriving (Show)

Строго говоря, мне для этого не нужны потоки; Стандартные списки Haskell идеально подходят для этой задачи. Но мне нравятся потоки, и они немного упрощают сопоставление с образцом (потому что мне не нужно иметь дело с пустым списком).

Затем я определяю тип направлений, а также функцию, определяющую, как они взаимодействуют с точками:

-- Note: I can’t use plain Left and Right
-- since they conflict with constructors
-- of the ‘Either’ data type
data Dir = LeftDir | RightDir | Up | Down deriving (Show)

type Point = (Int, Int)

move :: Dir -> Point -> Point
move LeftDir (x,y)  = (x-1,y)
move RightDir (x,y) = (x+1, y)
move Up (x,y)       = (x,y+1)
move Down (x,y)     = (x,y-1)

Теперь перейду к самой проблеме. Я определю два потока - один для направлений, а другой для количества повторений каждого направления:

dirStream :: Stream Dir
dirStream = Stream RightDir $ Stream Down $ Stream LeftDir $ Stream Up dirVals

numRepsStream :: Stream Int
numRepsStream = go 1
  where
    go n = Stream n $ Stream n $ go (n+1)

На этом этапе нам понадобится функция для репликации каждого элемента потока определенное количество раз:

replicateS :: Stream Int -> Stream a -> Stream a
replicateS (Stream n ns) (Stream a as) = conss (replicate n a) $ replicateS ns as
  where
    -- add more than one element to the beginning of a stream
    conss :: [a] -> Stream a -> Stream a
    conss [] s = s
    conss (x:xs) s = Stream x $ appends xs s

Это дает replicateS dirStream numRepsStream для потока направлений. Теперь нам просто нужна функция для преобразования этих направлений в координаты, и мы решили проблему:

integrate :: Stream Dir -> Stream Point
integrate = go (0,0)
  where
    go p (Stream d ds) = Stream p (go (move d p) ds)

spiral :: Stream Point
spiral = integrate $ replicateS numRepsStream dirStream

К сожалению, печатать бесконечный поток несколько неудобно, поэтому для отладки и печати полезна следующая функция:

takeS :: Int -> Stream a -> [a]
takeS 0 _ = []; takeS n (Stream x xs) = x : (takeS (n-1) xs)