的列表`dist`功能

Question

應用型分銷商，我認爲，我從Applicative Programming with Effects複製以下dist功能：

本文前言此函數：

Have you noticed that sequence and transpose now look rather alike? The details that distinguish the two programs are inferred by the compiler from their types. Both are instances of the applicative distributor for lists

dist :: Applicative f => [f a] -> f [a] 
dist []  = [[]] 
dist (v : vs) = [(:) v (dist vs)] 

不過，我得到以下編譯時錯誤：

ghci> :l ApplicativePaper.hs 
[1 of 1] Compiling Main    (ApplicativePaper.hs, interpreted) 

ApplicativePaper.hs:12:20: 
    Could not deduce (a ~ f a) 
    from the context (Applicative f) 
     bound by the type signature for 
       dist :: Applicative f => [f a] -> f [a] 
     at ApplicativePaper.hs:10:9-39 
     `a' is a rigid type variable bound by 
      the type signature for dist :: Applicative f => [f a] -> f [a] 
      at ApplicativePaper.hs:10:9 
    Relevant bindings include 
     vs :: [f a] (bound at ApplicativePaper.hs:12:9) 
     v :: f a (bound at ApplicativePaper.hs:12:7) 
     dist :: [f a] -> f [a] (bound at ApplicativePaper.hs:11:1) 
    In the first argument of `(:)', namely `v' 
    In the expression: (:) v (dist vs) 
Failed, modules loaded: none. 

請讓我知道我在做什麼NG。另外，請提供此功能的直覺。

Answer 1

在本文中，雙括號〚 f u1 … un 〛在第4頁定義爲與pure f <*> u1 <*> … <*> un相同。

在文本的dist定義是

dist :: Applicative f ⇒ [f a] → f [a ] 
dist []  = 〚 [] 〛 
dist (v : vs) = 〚 (:) v (dist vs) 〛 

翻譯其它符號到Haskell和製造用於的〚 … 〛結果定義中的取代在

dist :: Applicative f => [f a] -> f [a ] 
dist []  = pure [] 
dist (v : vs) = pure (:) <*> v <*> (dist vs) 

Answer 2

錯誤括號。 Conor McBride和Ross Paterson使用所謂的成語括號。這裏是你想象中的語法定義（但它可能與斯特拉斯克萊德哈斯克爾增強編譯，我不知道）：

dist :: Applicative f => [f a] -> f [a] 
dist []  = (| [] |) 
dist (v : vs) = (| (:) v (dist vs) |) 

(| f x y z |)闡述到pure f <*> x <*> y <*> z。所以dist定義權

dist :: Applicative f => [f a] -> f [a] 
dist []  = pure [] 
dist (v : vs) = (:) <$> v <*> dist vs -- f <$> x == pure f <*> x 

有一個非常類似的功能，Control.Monad模塊中定義：

-- | Evaluate each action in the sequence from left to right, 
-- and collect the results. 
sequence  :: Monad m => [m a] -> m [a] 
{-# INLINE sequence #-} 
sequence ms = foldr k (return []) ms 
      where 
       k m m' = do { x <- m; xs <- m'; return (x:xs) } 

只有它需要一個單子，而不是一個適用。

還有的dist的推廣，由Traversable類型類提供：

sequenceA :: Applicative f => t (f a) -> f (t a) 

所以，你有一些t（這既是一種Functor和Foldable），而不是[]這裏。

的sequence

-- | Evaluate each action in the sequence from left to right, 
-- and collect the results. 

這種描述是非常詳盡的。例如

main = dist [print 3, print 4, print 5] 

打印

3 
4 
5 

因爲每個單子是一個應用性，dist工作正常這裏與IO單子。然而，這裏沒有必要收集結果。這就是爲什麼有sequence_函數，因此返回()。

可以很容易地定義dist_：

dist_ :: Applicative f => [f a] -> f() 
dist_ []  = pure() 
dist_ (v : vs) = v *> dist_ vs 

所以只需在列表中執行所有操作。

例如

main = do 
    print $ dist_ [Just 3, Just 4, Just 5] 
    print $ dist_ [Nothing, Just 3] 

打印

Just() 
Nothing 

因爲

Just smth1 *> Just smth2 == Just smth2 
Nothing *> Just smth2 == Nothing 

的唯一的事情，那dist增加了這款機器，正在收集結果。

所以

main = do 
    print $ dist [Just 3, Just 4, Just 5] 
    print $ dist [Just 3, Nothing] 

打印

Just [3,4,5] 
Nothing 

而且，看看在Typeclassopedia。