Вложенные списки в Haskell

Question

Я следую за этим Haskell tutorial и нахожусь в разделе функций более высокого порядка. Она определяет функцию, называемую цепочку как:

chain :: (Integral a) => a -> [a] 
chain 1 = [1] 
chain n 
    | even n = n:chain (n `div` 2) 
    | odd n = n:chain (n * 3 + 1) 

Существует упражнение, чтобы найти количество «цепочек», которые имеют длину больше, чем 15. Они делают это так:

numLongChains :: Int 
numLongChains = length (filter isLong (map chain [1..100])) 
    where isLong xs = length xs > 15 

Я пытаюсь чтобы понять, что вместо того, чтобы дать мне количество цепочек, я даю список цепочек, которые длиннее 15 из [1..100]. Моя ближайшая попытка до сих пор выглядит следующим образом:

[ [ a | a <- chain b, length a > 15] | b <- [1..100]] 

, но я получаю:

<interactive>:9:14: 
No instance for (Integral [a0]) arising from a use of `chain' 
Possible fix: add an instance declaration for (Integral [a0]) 
In the expression: chain b 
In a stmt of a list comprehension: a <- chain b 
In the expression: [a | a <- chain b, length a > 15] 

<interactive>:9:45: 
    No instance for (Enum [a0]) 
     arising from the arithmetic sequence `1 .. 100' 
    Possible fix: add an instance declaration for (Enum [a0]) 
    In the expression: [1 .. 100] 
    In a stmt of a list comprehension: b <- [1 .. 100] 
    In the expression: 
     [[a | a <- chain b, length a > 15] | b <- [1 .. 100]] 

<interactive>:9:46: 
    No instance for (Num [a0]) arising from the literal `1' 
    Possible fix: add an instance declaration for (Num [a0]) 
    In the expression: 1 
    In the expression: [1 .. 100] 
    In a stmt of a list comprehension: b <- [1 .. 100] 

Am Я даже близко? Я хочу решить эту проблему, используя вложенное понимание ради обучения, несмотря на возможные более эффективные способы приблизиться к этому.

Answer 1

Вы близко. Вы ищете:

[ a | b <- [1..10], let a = chain b, length a > 15 ] 

Выражение

[ [ a | a <- chain b, length a > 15] | b <- [1..100]] 

имеет вид:

Integral [a] => [[[a]]] 

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

В этом случае b выводится как список некоторых типов, и именно поэтому вы видите сообщение об ошибке:

No instance for (Integral [a0]) ... 

Вот полный бег вниз на как типы случайны.

1. из b <- [1..100] мы можем сделать вывод, Enum b является ограничение
2. от вызова chain b мы можем сделать вывод, Integral b является ограничение
3. из a <- chain b мы можем сделать вывод a и b имеют одинаковый тип
4. из length a мы может вывести a - это список чего-то, например a ~ [t]

Так из (3) и (4) мы можем сделать вывод, что b ~ [t] и поэтому нам нужно как Integral [t] и Enum [t] для некоторого типа t.

Для дальнейшего уточнения (3) мы знаем, что chain b - это список, например. [t], где t - тип b. От a <- chain b мы знаем, что a имеет тот же тип, что и элементы chain b, то есть тип a также является t.