3

我已经意识到，当我嵌套了数据结构时，我一直在手动编写代码来深入研究它们。像这样：

--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. 我不知道如何解决这个问题 - 我是否应该编写代码来重复应用程序，即使那是我认为 iterate 的用途？
  3. 这似乎类似于“提升”的概念——但我不知道如何应用这种直觉。
4

2 回答 2

9

问题是这些“迭代”有不同的类型。对于每次迭代，您都会获得额外的嵌套级别，因此您想要

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)]
于 2012-10-18T03:09:18.187 回答
3

想想(iterate map f) !! n. 您希望它是a -> afor n = 0, [a] -> [a]for n = 1, [[a]] -> [[a]]for n = 2- 通常，您希望此表达式的类型取决于的值。n但这在 Haskell 中是不可能的，因为它不是一种依赖类型的语言。

于 2012-10-18T03:09:48.340 回答