要求澄清麦克布莱德/帕特森应用论文中的换位示例

Question

Conor McBride和Ross Paterson的经典论文具有效果的应用编程显示"矩阵"换位示例：

transpose   :: [[a]] -> [[a]]
transpose [] = repeat []
transpose (xs : xss) = zipWith (:) xs (transpose xss)

transpose正在使用列表的"收集观点"：它配对函数（此处(:)）和元素输入并生成结果列表输出。

因此，鉴于

v = [[1,2,3],[4,5,6]]

然后

transpose  v

结果在

[[1,4],[2,5],[3,6]]

后来在论文中他们说

如果我们想对转置示例做同样的事情，我们将不得不避免图书馆的"成功清单"（Wadler，1985）monad并采取而是支持"矢量化"的实例Applicative []，其中pure = repeat和(~) = zapp，产生

transpose'' :: [[a]] -> [[a]]
transpose''         [] = pure []
transpose'' (xs : xss) = pure (:) <*> xs <*> transpose'' xss

在这里，transpose''使用的是"非确定性计算点视图"的列表：它将函数（此处(:)）应用于输入转。

因此

 transpose'' v

结果在

 [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

我觉得我错过了一些微妙的点。 我可以看到transpose是确实使用收集视角转置"向量"列表。 但是transpose''（使用非确定性计算列表的观点）似乎与向量无关调换。

换句话说，transpose和transpose''似乎无关函数 - 不同的示例。 我错过了什么吗？

Answer 1

pure = repeat和(❄) = zapp的地方，屈服...

这不是标准列表实例。要在 Haskell 中实现这一点，我们需要

newtype Zapp a = Zapp { runZapp : [a] } deriving (Functor)
zcons :: a -> Zapp a -> Zapp a
zcons x (Zapp xs) = Zapp $ x : xs
instance Applicative Zapp where
  pure = Zapp . repeat
  Zapp a <*> Zapp b = Zapp $ zapp a b

然后

transpose'' :: Zapp (Zapp a) -> Zapp (Zapp a)
transpose''         (Zapp []) = pure $ Zapp []
transpose'' (Zapp (xs : xss)) = pure zcons <*> xs <*> transpose'' xss

Answer 2

如果为第一个示例列出实例，其中Applicative实例具有pure = repeat和<*> = zapp

instance Applicative [] where
    pure = repeat
    (<*>) = zapp
transpose :: [[a]] -> [[a]]
transpose         [] = pure []
transpose (xs : xss) = pure (:) <*> xs <*> transpose xss
main = do
    print . transpose $ [[1,2,3],[4,5,6]]

你从转置中获得换位：

[[1,4],[2,5],[3,6]]

相反，如果您使用普通Applicative实例进行[]

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
transpose :: [[a]] -> [[a]]
transpose         [] = pure []
transpose (xs : xss) = pure (:) <*> xs <*> transpose xss
main = do
    print . transpose $ [[1,2,3],[4,5,6]]

你得到

[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

这两个示例的样板是：

module Main (
    main
) where
import Prelude hiding (repeat)
infixl 4 <*>
class Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
repeat :: a -> [a]
repeat x = x : repeat x
zapp :: [a -> b] -> [a] -> [b]
zapp (f : fs) (x : xs) = f x : zapp fs xs
zapp _        _        = []