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

我已经意识到，当我嵌套数据结构时，我一直在手动编写代码来深入研究它们。就像这样：为什么我不能使用迭代来重复应用地图？

--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)'

它给我的印象是

我理解它找到一个列表，其中，预计...别的
我不知道如何解决这一问题 - 我应该令状e代码做重复的应用程序，即使这是我认为迭代的目的？
这似乎与“提升”的概念类似 - 但我不知道如何应用这种直觉。

来源

2012-10-18 nont

问题是这些“迭代”有不同的类型。对于每次迭代，你会得到嵌套了一层额外的，所以你要

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

但iterate :: (a -> a) -> a -> [a]要求迭代都具有相同的类型。实际上，直接执行上述操作需要某种形式的依赖类型，因为返回类型取决于值n。

除非你有充分的理由不这么做，否则我建议保持简单，只需要写出所需数量的map调用。可以使用模板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-18 03:09:18 hammar

谢谢！作为一个相对的Haskell noob，这可能是我第一次碰到一个表示语言限制的错误，而不仅仅是我理解的限制！现在...学习一些Agda :) – nont

它不是不可能的 - 它不建议新手尝试这样的事情，因为它们不是惯用的。如果您有充分的理由这样做，那么您应该明确地询问是否可以使用高级功能，如类型级别的数字。如果可以在Agda中表达，那么可能有可能在Haskell中表达，因为它有很多类型级别的机器，通常以依赖型语言存在。 – nponeccop

想想的(iterate map f) !! n类型。你希望它是a -> a为n = 0，[a] -> [a]为n = 1，[[a]] -> [[a]]为n = 2 - 一般情况下，你想这个表达式的类型依赖于价值n。但是这在Haskell中是不可能的，因为它不是一种依赖类型的语言。

来源

2012-10-18 03:09:48

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

回答

相关问题