Почему я не могу использовать итерацию для повторного применения карты?

Question

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

--one level 
Prelude> map (*2) [1,2,3] 
[2,4,6] 

--nested two levels 
Prelude> let t2 = map $ map (*2) 
Prelude> t2 [[1,2,3],[4,5,6]] 
[[2,4,6],[8,10,12]] 

--nested three levels 
Prelude> let t3 = map $ map $ map (*2) 
Prelude> t3 [[ [1,2,3],[4,5,6] ],[ [1,2,3],[4,5,6] ]] 
[[[2,4,6],[8,10,12]],[[2,4,6],[8,10,12]]] 

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

Prelude> let t f n = (iterate map f) !! n 

<interactive>:35:22: 
    Occurs check: cannot construct the infinite type: b0 = [b0] 
    Expected type: (a0 -> b0) -> a0 -> b0 
     Actual type: (a0 -> b0) -> [a0] -> [b0] 
    In the first argument of `iterate', namely `map' 
    In the first argument of `(!!)', namely `(iterate map f)' 

Ее поражает меня, что

1. Я понимаю его найти список, где он ожидал ... что-то еще
2. я не знаю, как это исправить - я предписание e, чтобы делать повторное приложение, хотя это то, на что я думал, что итерация была?
3. Это похоже на концепцию «подъема» - но я не знаю, как применить эту интуицию.

Answer 1

Проблема в том, что эти «итерации» имеют разные типы. Для каждой итерации, вы получаете дополнительный уровень вложенности, так что вы бы хотели

t f 0 :: a -> b 
t f 1 :: [a] -> [b] 
t f 2 :: [[a]] -> [[b]] 

Но iterate :: (a -> a) -> a -> [a] требует, чтобы витки имеют одинаковый тип. Фактически, прямая реализация вышеизложенного потребует некоторых форм зависимых типов, поскольку тип возврата зависит от значения n.

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

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

Вот краткий пример:

> import Data.Generics 
> let t x = everywhere (mkT (*2)) x 
> :t t 
t :: Data a => a -> a 
> t [2,4,6] 
[4,8,12] 
> t [[2,4,6],[8,10,12]] 
[[4,8,12],[16,20,24]] 
> t (Just [(1, 2, 3), (4, 5, 6)]) 
Just [(2,4,6),(8,10,12)] 

Answer 2

Подумайте о типе (iterate map f) !! n. Вы хотите, чтобы это было a -> a для n = 0, [a] -> [a] для n = 1, [[a]] -> [[a]] для n = 2 - в общем, вы хотите, тип этого выражения зависит от значения из n. Но это невозможно сделать в Haskell, поскольку это не язык, на котором набирается зависимость.