如何將函數映射到Haskell中的多級列表

Question

這是我在這裏的第一篇文章，我必須自我介紹說我是一名Haskell初學者。我喜歡純函數式編程的承諾，但經過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

您正在使用的功能

foldl (.) id (replicate depth map) 

而且

foldl (.) id (replicate 3 negate) 

第二編譯，但先不，爲什麼呢？

錯誤我們建議，在某些時候，編譯器找到一個表達式，必須是a和[a]，這並不是顯而易見的原因。 a類型不能與[a]類型相同，否則您將獲得無限嵌套列表，這些列表永遠無法評估任何內容。因此，讓我們看看我們的類型GHCI

> :t replicate 3 map 
replicate 3 map :: [(a -> b) -> [a] -> [b]] 
> :t replicate 3 negate 
replicate 3 negate :: Num a => [a -> a] 

這是我們的第二個線索中，replicate 3 map類型比replicate 3 negate完全不同的，如果我們忽略了Num a

[(a -> b) -> [a] -> [b]] 
-- Compared to 
[a -> a] 

前者有兩個參數，而第二隻有1.因此，如果我們手動查看類型，我們繼續添加另一個組合，會發生什麼？

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

因此，我們可以看到一個模式形成，每個組合添加一個列表嵌套。併爲negate？

> :t negate 
negate :: Num a => a -> a 
> :t negate . negate 
negate . negate :: Num a => a -> a 
> :t negate . negate . negate 
negate . negate . negate :: Num a => a -> a 

在這裏我們看到了不同的模式，每個組合都根本不會改變類型。這很重要嗎？

嗯，foldl類型是

> :t foldl 
foldl :: (a -> b -> a) -> a -> [b] -> a 

所以輸出型完全由第一個參數確定的。類型本身與輸入列表的類型或它有多少元素無關。更具體地說

> :t foldl (.) id 
foldl (.) id :: [a -> a] -> a -> a 

而且[a -> a]不符合我們的地圖[(a -> b) -> [a] -> [b]]的類型。事實上，因爲Haskell的類型箭頭是右關聯，這意味着編譯器正試圖排隊類型，

[c  -> c   ] 
[(a -> b) -> ([a] -> [b])] 

所以c ~ a -> b和c ~ [a] -> [b]，所以後來(a -> b) ~ ([a] -> [b])這意味着a ~ [a]和b ~ [b]。這是編譯器錯誤的來源。

---

現在你可能會問這個問題：「我如何在Haskell中完成這種事情？」答案可能讓你失望，你通常不會。類型非常嚴格，所以不會有這樣的情況，您可以選擇將[Int]或[[Int]]或[[[Int]]]傳遞給單個函數，但它不會編譯。我不知道解決這個問題的方法，但是@Lee建議我可以解答鏡頭套件（我沒有太多經驗）。鏡頭具有非常普遍的類型，所以很可能有一個可以使用Traversal將其很好地概括爲任何級別的嵌套。

Answer 2

你所要求的是不可能的（至少很難），儘管起初很難看清楚。

此處分析的適當工具是編譯時/運行時區別出現在您的代碼中。具體來說，假設我們有一個函數maps，這樣maps 3 f將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操作擴展爲維數組。只要我們在編譯時（再次，將是一個有點挑戰性的逃脫），那麼我們也可以被明確這個想法

newtype TwoD a = TwoD { getLists2d :: [[a]] } 
newtype ThreeD a = ThreeD { getLists3d :: [[[a]]] } 
newtype FourD a = FourD { getLists4d :: [[[[a]]]] } 
-- etc... 

現在這些每一個有固定nmap的自然延伸。事實上，這種想法多種類型是的「map pable」是Functor類型類的完全的直覺，所以我們可以實例它們都作爲Functor小號

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爲類似於「口齒不清」式列表，即任意嵌套的樹木。

(('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樹的特定「層」，因此不能統一更改其中每個值的類型。要做到這一點，我們仍然必須使用我們派生的Functor實例中的fmap。