在 Haskell 中映射任意深度的列表

Question

可以映射任意深度的列表列表，如下所示：

map           :: (a -> b) ->   [a]   ->   [b]
(map.map)     :: (a -> b) ->  [[a]]  ->  [[b]]
(map.map.map) :: (a -> b) -> [[[a]]] -> [[[b]]]

是否可以编写一个函数来处理所有此类情况？ Uiua 具有

∵ each

函数，可以在任意等级的数组上执行此操作。此类函数在数组语言中称为普适函数。

Answer 1

嵌套列表可能太笼统，无法有效地指导类型推断，因此尽管将

deepmap

实现为类型类非常简单：

class DeepMap a b a' b' where
  deepmap :: (a -> b) -> [a'] -> [b']

instance DeepMap a b a b where
  deepmap = map
instance (DeepMap a b a' b') => DeepMap a b [a'] [b'] where
  deepmap = map . deepmap

你必须向类型检查器提供很多指导才能使用它：

main = do
  print $ deepmap @Int @Int @Int @Int (*2) $ [1,2]
  print $ deepmap @Int @Int @[Int] @[Int] (*2) $ [[1],[2]]

如果

DeepMap

类的所有四个类型参数都由上下文解析，那么它就可以正常工作：

main = do
    print $ (deepmap ord ["ab","c"] :: [[Int]])

在实际代码中，您可能会引入一种新的数据类型来表示此类数组，例如具有数组等级的类型级索引的 GADT。 （如果您真的想用“数组语言”来表示术语，则通过表示维度的

[Int]

类型进行索引可能更有意义。）

data Nat = Z | S Nat

data Array n a where
  Scalar :: a -> Array Z a
  Array :: [Array n a] -> Array (S n) a
deriving instance (Show a) => Show (Array Z a)
deriving instance (Show (Array n a)) => Show (Array (S n) a)

这种类型允许非常简单的

deepmap

实现：

deepmap :: (a -> b) -> Array n a -> Array n b
deepmap f (Scalar x) = Scalar (f x)
deepmap f (Array xs) = Array (fmap (deepmap f) xs)

main = do
  print $ deepmap (*2) $ Scalar 1
  print $ deepmap (*2) $ Array [Scalar 1, Scalar 2]
  print $ deepmap (*2) $ Array [Array [Scalar 1], Array [Scalar 2]]