为什么我不能使用迭代重复应用地图？

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. 我不知道如何解决这个问题 - 我应该编写代码来重复应用程序,即使这是我认为迭代的原因吗？
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)]