Список понятий - требуется базовый вариант?

Question

Я не понимаю, зачем нужен базовый случай в этом:

-- perms :: Ord a => [a] -> [[a]]
perms [] = [[]]
perms xs = [ (x:ps) | x <- xs, ps <- perms (xs \\ [x])]

Мне кажется, что он должен быть автоматическим из списка-понимания, но потом я заметил, что:

[ x:y | x<-[], y<-[] ]

оценивается как [], а не [[]], что кажется удивительным.

Несмотря на это, я также был удивлен, что без базового случая он работает, но всегда дает [],нарушает тип подписи.Есть ли простой способ отследить выполнение понимания списка?Debug.Trace.trace кажется атомарным.

Answer 1

Вы можете думать о <- как об использовании каждого элемента из списка справа в выражении слева. Поскольку [] не имеет элементов, понимание всего списка возвращает пустой список. Будет странно, если [ x:y | x<-[], y<-[] ] вернет [[]], потому что : берет элемент и список. Таким образом, для генерации [[]] у должно быть [], но тогда что будет x?

Как сказал Кенни ТМ, [] имеет тип [[a]]. На самом деле [] от каждого типа этого вида: [a] [[a]] [[[a]]] и так далее. Если этого не было, то функция не может вернуть пустой список.

Во всяком случае, очень распространенная ошибка - забывать некоторые скобки, и именно поэтому необходимы аннотации типов.

Answer 2

Давай без сахара!

[ x:y | x <- [], y <- [] ]

Превращается в

do x <- []
   y <- []
   return (x:y)

Теперь, больше обезвоживания! Ура!

[] >>= \x -> ([] >>= \y -> return (x:y))

iirc, >>= для списков - flip concatMap, а return - просто \x -> [x]

Давайте сделаем лишь небольшую часть этой замены.

concatMap (\x -> ([] >>= \y -> return (x:y))) []

Там, теперь вы видите? concatMap f [] явно оценивается в []. Потому что concatMap f это просто concat . map f. Поэтому сопоставьте f с пустым списком и затем объедините результаты. За исключением отсутствия результатов, итоговая оценка составляет [].

Answer 3

Таким образом, все сводится к значению

[ x:y | x<-[], y<-[] ]

. Способ чтения: «Каковы возможные значения x:y, когда x не имеет возможных значений, и * 1006»* не имеет возможных значений? "Надеюсь, должно быть ясно, что в этом случае вообще нет значений для x:y, так как вам потребуется значение для x и значение для y, чтобы получить возможность для x:y, иу вас нет ни одного.

Эта общая схема выбора комбинаций возможных значений для x и y называется декартовым произведением , и слово "продукт" используется частично потому, чтоколичество возможных комбинаций равно количеству возможностей для x, раз количество возможностей для y.Поэтому, если для x есть ноль вариантов, а для y - ноль, можно ожидать 0 * 0 = 0 вариантов для комбинаций этих двух.

Answer 4

Если у вас есть понимание списка формы:

[ x:y | stuff ]

затем вы создаете список, элементы которого имеют форму x:y для некоторых вариантов x и y, как определено stuff. [[]] - это список, элементы которого не имеют формы x:y для любого x или y, поэтому первый не может создать последний.

Ожидая [[]] от [ x:y | x <- [], y <- [] ], вы, похоже, устанавливаете x = [] и y = [], а затем рассматриваете x:y = [[]]. Это неправильно по нескольким причинам:

• x происходит от xs типа [a], поэтому x имеет тип a и не является (вообще) списком
• результатом понимания списка является список из x:y элементов, а не один.

Answer 5

Вот еще один намек, почему существует базовый случай с пустым списком.Сколько существует перестановок n элементов?Есть n! перестановок.А что такое 0!?Это 1. Таким образом, длина списка результатов для perm [] должна быть 1. Типы и отсутствие элементов типа a приводят к тому, что результат будет [[]].Ни одно другое определенное значение не имеет правильного типа и длины.