Способна ли обнаружение циклических списков в Haskell нарушать любые свойства языка?

В Haskell некоторые списки циклические:

ones = 1 : ones

Других нет:

nums = [1..]

И тогда есть такие вещи:

more_ones = f 1 where f x = x : f x

Это означает то же значение, что и ones, и, конечно, это значение является повторяющейся последовательностью. Но сомнительно ли оно представлено в памяти как циклическая структура данных. (Реализация может сделать это, но этот ответ объясняет, что "маловероятно, что это произойдет на практике" .

Предположим, что мы берем реализацию Haskell и взламываем в нее встроенную функцию isCycle :: [a] -> Bool, которая анализирует структуру представления аргумента в памяти. Он возвращает True, если список физически цикличен и False, если аргумент имеет конечную длину. В противном случае он не завершится. (Я предполагаю, что "взломал его", потому что невозможно записать эту функцию в Haskell.)

Будет ли существование этой функции нарушать любые интересные свойства языка?

Ответы

Ответ 1

Будет ли существование этой функции нарушать какие-либо интересные свойства языка?

Да. Это нарушит ссылочную прозрачность (см. Также статья в Википедии). Выражение Haskell всегда можно заменить на его значение. Другими словами, это зависит только от переданных аргументов и ничего другого. Если бы мы имели

isCycle :: [a] -> Bool

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

fmap id === id

больше не будет: вы могли бы различать ones и fmap id ones, поскольку последний был бы ацикличным. И оптимизация компилятора, такая как применение вышеуказанного закона, больше не сохранит свойства программы.

Однако другой вопрос будет иметь функцию

isCycleIO :: [a] -> IO Bool

в качестве IO действий разрешено исследовать и изменять что-либо.

Чистым решением может быть тип данных, который внутренне различает два:

import qualified Data.Foldable as F

data SmartList a = Cyclic [a] | Acyclic [a]

instance Functor SmartList where
    fmap f (Cyclic xs) = Cyclic (map f xs)
    fmap f (Acyclic xs) = Acyclic (map f xs)

instance F.Foldable SmartList where
    foldr f z (Acyclic xs) = F.foldr f z xs
    foldr f _ (Cyclic xs) = let r = F.foldr f r xs in r

Конечно, он не сможет распознать, является ли общий список циклическим или нет, но для многих операций можно было бы сохранить знание значений Cyclic.

Ответ 2

В общем случае нет, вы не можете идентифицировать циклический список. Однако, если список создается с помощью операции разворота, вы можете. Data.List содержит следующее:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

Первый аргумент - это функция, которая принимает аргумент "состояние" типа "b" и может возвращать элемент списка и новое состояние. Второй аргумент - это начальное состояние. "Nothing" означает, что список заканчивается.

Если состояние когда-либо повторяется, список будет повторяться с точки последнего состояния. Поэтому, если вместо этого использовать другую функцию разворота, которая возвращает список (a, b), мы можем проверить состояние, соответствующее каждому элементу. Если одно и то же состояние отображается дважды, список цикличен. Конечно, это предполагает, что состояние является экземпляром Eq или что-то еще.