Как мне избежать <<loop>> в Haskell?

Question

Программа ниже приводит к <<loop>> в GHC.

...Очевидно. Задним числом.

Это происходит потому что walkвычисляет фиксированную точку, но существует несколько возможных фиксированных точек. Когда понимание списка достигает конца обхода графа, оно «запрашивает» следующий элемент answer; но это именно то, что он уже пытается вычислить. Думаю, я рассчитывал, что программа дойдёт до конца списка и остановится.

Должен признаться, я немного сентиментален по поводу этого красивого кода и хотел бы заставить его работать.

• Что мне делать вместо этого?

• Как я могу предсказать, когда «завязывать узел» (имея в виду значение внутри выражения, в котором говорится, как вычислить значение) - плохая идея?

      import Data.Set(Set)
import qualified Data.Set

-- Like `Data.List.nub`, remove duplicate elements from a list,
-- but treat some values as already having been seen.
nub :: Set Integer -> [Integer] -> [Integer]
nub _ [] = []
nub seen (x:xs) =
  if Data.Set.member x seen
  then nub seen xs
  else x : nub (Data.Set.insert x seen) xs

-- A directed graph where the vertices are integers.
successors :: Integer -> [Integer]
successors x = [(x + 2) `mod` 7, (x + 3) `mod` 7]

-- Breadth first search of a directed graph.  Returns a list of every integer
-- reachable from a root set in the `successors` graph.
walk :: [Integer] -> [Integer]
walk roots =
  let rootSet = Data.Set.fromList roots
      answer = roots ++ nub rootSet [y | x <- answer, y <- successors x]
  in answer

main = putStrLn $ show $ walk [0]

Answer 1

Вот одна идея, как это исправить: ну, нам нужно условие завершения, верно? Итак, давайте сохраним достаточно структуры, чтобы знать, когда нам следует завершить работу. В частности, вместо создания потока узлов мы создадим поток границ и остановимся, когда текущая граница станет пустой.

      import Data.Set(Set)
import qualified Data.Set as S

-- Like `Data.List.nub`, but for nested lists. Order in inner lists is not
-- preserved. (A variant that does preserve the order is not too hard to write,
-- if that seems important.)
nestedNub :: Set Integer -> [[Integer]] -> [[Integer]]
nestedNub _ [] = []
nestedNub seen (xs_:xss) = S.toList xs : nestedNub (seen `S.union` xs) xss where
  xs = S.fromList xs_ `S.difference` seen

-- A directed graph where the vertices are integers.
successors :: Integer -> [Integer]
successors x = [(x + 2) `mod` 7, (x + 3) `mod` 7]

walk :: [Integer] -> [Integer]
walk roots =
  let answer = nestedNub S.empty
        $ roots
        : [[y | x <- frontier, y <- successors x] | frontier <- answer]
  in concat $ takeWhile (not . null) answer

main = print $ walk [0]

Почти наверняка не существует общего алгоритма для определения того, что завязывание узла - плохая идея - мое чутье говорит, что это проблема, и я признаю, что не пытался проработать детали!

Answer 2

Глядя на ваш код, можно предположить, что мы должны иметь возможность получить по крайней мере root префикс answer, так как это не зависит от завязки узла. И конечно же:

      GHCi> take 1 $ walk [0]
[0]

Мы можем пойти еще дальше:

      GHCi> take 7 $ walk [0]
[0,2,3,4,5,6,1]

Однако, как только мы просим элемент восемь, мы застреваем:

      GHCi> take 8 $ walk [0]
[0,2,3,4,5,6,1

(Интересно, что попытка его использования в GHCi не вызывает срабатывания детектора <<loop>>, в отличие от скомпилированной программы.)

Проблема проявляется только тогда, когда выходит за рамки седьмого элемента списка уникальных целых чисел по модулю 7, что указывает на суть проблемы. Удаление из вашего определения дает нам прекрасный бесконечный список:

      walkWithDuplicates :: [Integer] -> [Integer]
walkWithDuplicates roots =
  let rootSet = Data.Set.fromList roots
      answer = roots ++ [y | x <- answer, y <- successors x]
  in answer

      GHCi> (!! 9999) $ walkWithDuplicates [0]
2

С помощью nubв бесконечном списке - рискованный бизнес. Если количество различных элементов в нем конечно, в какой-то момент не будет производиться следующий элемент.

Что же тогда делать? Если мы заранее знаем размер графа, как в вашем примере, мы можем весело схитрить:

      walkKnownSize :: [Integer] -> [Integer]
walkKnownSize roots =
  let graphSize = 7
      rootSet = Data.Set.fromList roots
      answer = roots ++ nub rootSet [y | x <- answer, y <- successors x]
  in take graphSize answer

      GHCi> walkKnownSize [0]
[0,2,3,4,5,6,1]

(Обратите внимание, что указание размера графика совсем не походило бы на обман, если бы мы передавали ваш график функции как тройной размер, корни и Int -> Integer -> [Integer] функции преемников.)

В дополнение к этому и к альтернативной стратегии завязывания узлов Даниэля Вагнера, я считаю, что для полноты картины стоит предложить решение без завязывания узлов. Приведенная ниже реализация представляет собой разворачивание, которое генерирует последовательные уровни ходьбы (в духе предложения Ли Яо Ся ). Это дает возможность остановиться после посещения всех элементов:

      import Data.List (unfoldr)
-- etc.

walkUnfold :: [Integer] -> [Integer]
walkUnfold roots =
    let rootsSet = Data.Set.fromList roots
        nextLevel (previouslySeen, currentLevel) =
            let seen = foldr Data.Set.insert previouslySeen currentLevel
                candidates = concatMap successors currentLevel
                newlyVisited = nub seen candidates
            in case newlyVisited of
                [] -> Nothing
                _ -> Just (newlyVisited, (seen, newlyVisited))
        levels = roots : unfoldr nextLevel (Data.Set.empty, roots)
    in concat levels