这是我在这里的第一篇文章,我必须自我介绍说我是Haskell的初学者.我喜欢纯函数式编程的承诺,但经过20年的命令式编程(主要是Java)之后,Haskell对我来说并不自然.
所以这是我的第一个问题.我正在尝试将函数映射到多级列表.此代码有效,但映射发生的列表的深度级别预设为3:
(map . map . map) (+1) [[[1,4],[2,3]],[[5]]]
我需要更通用的东西,我指定映射发生的级别(下面一行中的深度参数),如下所示:
let depth = 3 :: Int
(foldl (.) id (replicate depth map)) (+1) [[[1,4],[2,3]],[[5]]]
不幸的是,这不起作用,我得到这个错误:
Occurs check: cannot construct the infinite type: t0 = [t0]
Expected type: ([[[t0]]] -> [[[t0]]]) -> [[[t0]]] -> [[[t0]]]
Actual type: ([[[t0]]] -> [[[t0]]]) -> [[[[t0]]]] -> [[[[t0]]]]
In the second argument of `replicate', namely `map'
In the third argument of `foldl', namely `(replicate depth map)'
In the expression:
(foldl (.) id (replicate depth map))
(+ 1) [[[1, 4], [2, 3]], [[5]]]
但是,此代码有效:
foldl (.) id (replicate 3 negate) $ 7
同样,问题是:如何将函数映射到多级列表,其中列表的深度是预先知道的.我想做的事情如下:
(foldl (.) id (replicate 3 map)) (+1) [[[1,4],[2,3]],[[5]]]
并得到这个结果:
[[[2,5],[3,4]],[[6]]]
先感谢您.
你要求的是不可能的(至少是困难的)虽然起初很难看到.
这里适当的分析工具是代码中出现的编译时/运行时区别.特别是,假设我们有一个函数maps,可以maps 3 f映射f到列表的第三层.它的类型是什么？好吧,我们可以写出来
maps 1 :: (a -> b) -> [a] -> [b]
maps 2 :: (a -> b) -> [[a]] -> [[b]]
maps 3 :: (a -> b) -> [[[a]]] -> [[[b]]]
...
这可能已经看起来很奇怪,但如果它没有那么认真地注意到什么是怎么回事:终极型的maps n f取决于价值的n,这东西只能在运行时是已知的.
因为我们必须在编译时对事物进行类比检查,并且存在maps意味着我们无法知道maps n不知道运行时值的类型n然后我们就会陷入困境.这样的功能,maps不可能存在.
理论上无论如何.在实践中,我们当然可以解决这种情况.但是,正如通常存在类型错误时一样,我们首先必须更清楚地了解我们正在努力实现的目标.
这个函数的第一个解释是我们想要将map操作扩展到一个n维数组.只要我们n在编译时修复(再次,这将是一个有点挑战逃避)那么我们也可以明确这个想法
newtype TwoD a = TwoD { getLists2d :: [[a]] }
newtype ThreeD a = ThreeD { getLists3d :: [[[a]]] }
newtype FourD a = FourD { getLists4d :: [[[[a]]]] }
-- etc...
现在这些中的每一个都具有自然延伸map.实际上,多种类型的" mappable" 这个概念正是Functor类型类的直觉,所以我们可以将它们全部实例化为Functors
instance Functor TwoD where fmap f (TwoD lists) = TwoD ((map . map) f lists)
instance Functor ThreeD where fmap f (ThreeD lists) = ThreeD ((map . map . map) f lists)
-- etc...
事实上,这是一个很自然的想法,GHC实现了一个扩展,它将Functor为我们推导出这些实例.
{-# LANGUAGE DeriveFunctor #-}
newtype TwoD a = TwoD { getLists2d :: [[a]] } deriving Functor
newtype ThreeD a = ThreeD { getLists3d :: [[[a]]] } deriving Functor
newtype FourD a = FourD { getLists4d :: [[[[a]]]] } deriving Functor
-- etc...
现在fmap可以n非常自然地在我们的任何数组类型上使用.
另一种可能的解释是,我们不想表示一个n维数组,而是代表一个"玫瑰树".不同之处在于,在n维数组中,每个值的"索引序列" 都是n元素长.例如,左上角的值在索引[0,0,0]在ThreeD.在Rose树中,我们有列表的混合,而不是每个值都在相同的深度.这意味着我们不再像使用类似对象那样[a]对列表深度进行静态保证[[[[a]]]],但这也意味着所有深度信息现在都在运行时发生.
哪个是我们想要的.
我们Rose先定义一下.
data Rose a = Rose [Rose a] | L a deriving Functor -- Functor for free!
我们还可以生成一个样本值,Rose Char以使其更清晰如何Rose工作.
Rose [Rose [L 'f', L 'o', L 'o', Rose [L 'x', L 'y', L 'z']], L 'b', L 'a', L 'r']
我喜欢将其Rose视为类似于"lisp"风格的列表,即任意嵌套的树.
(('f' 'o' 'o' ('x', 'y' 'z')) 'b' 'a' 'r')
然而,有趣的部分是,因为我们现在将Rose树的深度保留到运行时(实际上它可以在运行时动态变化),我们可以使用运行时信息来map覆盖它.
mapR :: Int -> (a -> a) -> Rose a
mapR 0 f (L a) = L (f a)
mapR n f (L a) = L a
mapR n f (Rose as) = Rose (map (mapR (n-1) f) as)
注意,与普通的不同map,mapR's函数参数不能改变类型Rose.这是因为我们只映射Rose树的特定"层",因此无法统一更改其中每个值的类型.为此,我们仍然必须使用fmap派生Functor实例.
您正在使用的功能是
foldl (.) id (replicate depth map)
和
foldl (.) id (replicate 3 negate)
第二个可以编译，但第一个不能，为什么？
我们建议的错误是，在某个时刻，编译器正在查找一个必须同时为a和 的表达式[a]，但出于明显的原因，这并非如此。typea不能与 type 相同[a]，否则您会得到无限嵌套的列表，这些列表永远不会计算出任何值。让我们看看 GHCi 中的类型
> :t replicate 3 map
replicate 3 map :: [(a -> b) -> [a] -> [b]]
> :t replicate 3 negate
replicate 3 negate :: Num a => [a -> a]
这是我们的第二条线索，如果我们忽略 的话，的类型与 的类型replicate 3 map有很大不同replicate 3 negateNum a
[(a -> b) -> [a] -> [b]]
-- Compared to
[a -> a]
前者有 2 个参数，而第二个只有 1 个参数。那么，如果我们在不断添加另一个组合的同时手动查看类型，会发生什么情况呢？
> :t map
map :: (a -> b) -> [a] -> [b]
> :t map . map
map . map :: (a -> b) -> [[a]] -> [[b]]
> :t map . map . map
map . map . map :: (a -> b) -> [[[a]]] -> [[[b]]]
所以我们可以看到一个模式正在形成，每个组合都添加了一个列表的嵌套。而为了negate？
> :t negate
negate :: Num a => a -> a
> :t negate . negate
negate . negate :: Num a => a -> a
> :t negate . negate . negate
negate . negate . negate :: Num a => a -> a
在这里我们看到了不同的模式，每种组合根本没有改变类型。这重要吗？
嗯，类型foldl是
> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
所以输出类型完全由第一个参数决定。类型本身与输入列表的类型或它有多少元素无关。进一步来说
> :t foldl (.) id
foldl (.) id :: [a -> a] -> a -> a
并且[a -> a]与我们的地图类型不匹配[(a -> b) -> [a] -> [b]]。事实上，由于 Haskell 的类型箭头是右关联的，这意味着编译器试图将类型排列为
[c -> c ]
[(a -> b) -> ([a] -> [b])]
So c ~ a -> band c ~ [a] -> [b], so then(a -> b) ~ ([a] -> [b])这意味着a ~ [a]and b ~ [b]。这是该编译器错误的根源。
现在你可能会问“我如何在 Haskell 中完成这类事情？” 答案可能会让你失望，但通常不会。类型非常严格，因此永远不会有这样的情况：您可以选择将[Int]or[[Int]]或[[[Int]]]传递给单个函数，但它无法编译。我不知道有什么办法可以解决这个问题，但正如 @Lee 所建议的，镜头包（我对此没有太多经验）可能就是答案。镜头具有非常通用的类型，因此很可能有一种可以将Traversal其很好地推广到任何级别的嵌套。