Haskell: распространенные ошибки Corecursive

Question

Итак, я подумал об алгоритме расстояния на графике сегодня вечером и придумал пока я ехал в машине:

module GraphDistance where
import Data.Map

distance :: (Ord a) => a -> Map a [a] -> Map a Int
distance a m = m' 
  where m' = mapWithKey d m
        d a' as = if a == a' then 0 else 1 + minimum (Prelude.map (m'!) as)

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

Мне пришлось закодировать это, чтобы убедить себя:

ghci> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])]
fromList [(0,1),(1,0),(2,^CInterrupted.

Но теперь я думаю, что в значительной степени продумал это.

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

Answer 1

Ну, на самом деле есть только одна фундаментальная ошибка при работе с corecursive данными, и это небрежно использовать рекурсию на них!

Corecursion подразумевает, что данные в некотором смысле генерируются постепенно. Ваша функция расстояния графика здесь поучительна, потому что кажется, что она должна работать, поэтому подумайте, где должна быть инкрементная часть: Начальная точка - это расстояние 0 от узла до самого себя, в противном случае на единицу больше, чем минимальное расстояние среди своих непосредственных соседей. Таким образом, мы ожидаем, что каждое значение расстояния будет инкрементным, а это означает, что мы нуждаемся в том, чтобы они сами были соответствующим образом активными.

Таким образом, рассматриваемая рекурсия происходит из-за комбинации (+) и minimum: при нахождении минимума 1 всегда будет меньше 1 + n, не беспокоясь о том, что n есть ... но нет способа сравнить Int с без вычисления всего значения.

Короче говоря, алгоритм ожидает, что он сможет сравнивать, сколько раз (1 +) применялось к 0 только настолько, насколько это необходимо; то есть он хочет ленивые натуральные числа, определенные с использованием «ноль» и «преемник».

Вот:

data Nat = Z | S Nat

natToInt :: Nat -> Int
natToInt Z = 0
natToInt (S n) = 1 + natToInt n

instance Show Nat where show = show . natToInt

instance Eq Nat where
    Z == Z = True
    (S n1) == (S n2) = n1 == n2
    _ == _ = False

    Z /= Z = False
    (S n1) /= (S n2) = n1 /= n2
    _ /= _ = True


instance Ord Nat where
    compare Z Z = EQ
    compare Z (S _) = LT
    compare (S _) Z = GT
    compare (S n1) (S n2) = compare n1 n2

А затем в GHCi:

> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])]
fromList [(0,1),(1,0),(2,1),(3,2)]

Доказательство того, что ваш алгоритм работает ^[0] ; ваша реализация была просто неправильной.

---

Теперь, в качестве небольшого изменения, давайте применим ваш алгоритм к другому графику:

> distance 1 $ fromList [(0,[1]),(1,[0]),(2,[3]),(3,[2])]

... что мы ожидаем от этого? Каково расстояние от узла 1 для узлов 2 или 3?

Запуск его в GHCi дает очевидный результат:

fromList [(0,1),(1,0),(2,^CInterrupted.

Тем не менее, алгоритм корректно работает на этом графике . Вы видите проблему? Почему он завис в GHCi?

---

Таким образом, вам нужно четко различать две формы, которые нельзя смешивать свободно:

• Ленивые, возможно бесконечные данные, сгенерированные corecursively
• Конечные данные, потребляемые рекурсивно

Обе формы могут быть преобразованы структурно-независимым способом (например, map работает как с конечным, так и с бесконечным списками). Кодата может потребляться постепенно, на основе алгоритма corecursive; данные могут быть сгенерированы рекурсивно, ограничены рекурсивным алгоритмом.

То, что вы не можете сделать, - это рекурсивно потреблять кодаты (например, сворачивать бесконечный список) или генерировать данные по центру (редко в Haskell, из-за лени).

[0] : На самом деле на некоторых входах произойдет сбой (например, на некоторых отключенных графиках), но это другая проблема.