Почему функция цикла не может работать с пустым списком?

Я использовал функцию cycle в некоторых моих проектах, и сегодня я обнаружил, что это не полная функция, как показано в этом Пример GHCI:

λ> Data.List.cycle []
*** Exception: Prelude.cycle: empty list

Я знаю, что Haskells пытается использовать полные функции (кроме основных функций head и tail), и я не совсем уверен, почему cycle не является одним из них. По-моему, cycle пустого списка - это пустой список, и я не вижу проблем с этим. Почему cycle для пустых списков выдает ошибку?

ИЗМЕНИТЬ: Основываясь на первых ответах, я думаю, что моя идея не совсем ясна: я не хочу, чтобы cycle [] был вычислением, которое никогда не заканчивается. Напротив, я думаю, что cycle [] должен быть следующим:

cycle :: [a] -> [a]
cycle [] = []
cycle xs = xs ++ cycle xs

[] - это cycle [], потому что все операции выполняют именно то, что я за исключением. Например, take 3 [] составляет [], и, таким образом, take 3 (cycle []) может быть []. Какая проблема с этим решением?

Ответ 1

У меня нет специального понимания ума (ов) людей, которые внедрили функцию cycle.

В предложении сказано следующее о цикле:

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

Традиционно, когда вы думаете о циклически связанном списке, запись в вики, у вас есть:

Как я могу выразить круглый пустой список? Указатель, идущий к себе? Но даже это не подходит.

Мое лучшее объяснение состоит в том, что круговые списки не являются нормальными списками. Это разные звери с разной семантикой. Точно так же, как head действительно является полным только для непустого пустого списка, потому что нет первого элемента пустого списка, cycle полностью определяется только для непустых списков, потому что нет пустого кругового связанного списка.

Ответ 2

cycle фактически определяется как возвращающий бесконечный список для всех входных данных. Если бы он попытался сделать это наивно с пустым входом, он сидел бы в бесконечном цикле. Условие ошибки немного более информативно с той же денотационной семантикой.

Изменить:

Поскольку люди, похоже, не понимают, что я имею в виду, когда говорю, что пустой результат плохой, рассмотрите эту простую функцию:

labelElements :: [a] -> [b] -> [(a, b)]
labelElements labels elements = zip (cycle labels) elements

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

Ответ 3

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

cycle' xs = xs ++ cycle' xs

take 3 (cycle' [1,2]) -- returns [1,2,1]
take 3 (cycle' [])    -- still looping

Ответ 4

Обратите внимание, что, поскольку он определен в настоящее время, он согласуется с tail.

tail [] = error ...

cycle концептуально связан с tail. Когда вы cycle список, это означает, что вы можете многократно смотреть на его tail и никогда не достигать "конца" ([]), потому что это цикл. (См. Изображение Davorak.) Другими словами, всегда безопасно использовать tail в списке cycle 'd, предполагая, что, конечно, безопасно использовать cycle в этом списке.

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

tail [] = []
cycle [] = []

Но вы должны переопределить как cycle, так и tail для согласованности.

Ответ 5

Цель cycle, как описано в документации:

import Data.List.Nonempty
import Data.Stream.Infinite

cycle :: NonEmpty a -> Stream a

Авторы Prelude используют частичную функцию для передачи в пустом списке, что является концептуальной ошибкой типа, аналогичной head и tail.

Если вам нужен цикл, который возвращает [], это будет просто:

myCycle :: [a] -> [a]
myCycle xs = if null xs then xs else cycle xs

См. semigroups для определения NonEmpty и streams для определения Stream и полного определения cycle.