list - 如何将函数映射到 Haskell 中的多级列表

Question

这是我在这里的第一篇文章，我必须通过说我是 Haskell 初学者来介绍自己。我喜欢纯函数式编程的 promise ，但是在 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]]]

先感谢您。

Answer 1

您所要求的是不可能的(至少是困难的)，尽管一开始很难看到这一点。

此处用于分析的正确工具是代码中出现的编译时/运行时区别。特别是，假设我们有一个函数 maps这样maps 3 f map 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 的自然扩展。 .事实上，多种类型为“ map pable”的想法正是 Functor 的直觉。 typeclass，所以我们可以将它们全部实例化为 Functor s

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的函数参数不能改变 Rose的类型.这是因为我们只是在 Rose 的特定“层”上进行映射。树，因此无法统一更改其中每个值的类型。为此，我们仍然必须使用 fmap来自我们的 Functor实例。