請求澄清

Question

康納麥克布萊德的和Ross帕特森的經典論文 Applicative programming with effects 示出了「矩陣的計算」換位例如：

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）單子，並採取 而不是支持「量化」的實例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 _  _  = []