瞭解哈斯克爾

Question

修復數據類型在this article關於免費單子Haskell中，我們給出了通過定義一個玩具的數據類型：

data Toy b next = 
    Output b next 
    | Bell next 
    | Done 

修復的定義如下：

data Fix f = Fix (f (Fix f)) 

它允許巢通過保留普通型玩具表達式：

Fix (Output 'A' (Fix Done))    :: Fix (Toy Char) 
Fix (Bell (Fix (Output 'A' (Fix Done)))) :: Fix (Toy Char) 

我知道如何固定點但是我沒有看到這裏的類型是如何減少的。編譯器遵循哪些步驟來評估表達式的類型？

Answer 1

我會用Fix來製作一個更爲熟悉，更簡單的類型，看看你是否會理解它。

下面是一個正常的遞歸定義列表類型：

data List a = Nil | Cons a (List a) 

現在，我們如何使用fix的功能回想起來，我們知道，我們必須給函數傳遞給自身作爲參數。事實上，自List是遞歸的，我們可以寫一個簡單的非遞歸數據類型，像這樣：

data Cons a recur = Nil | Cons a recur 

你能看到如何，這是類似的，比方說，功能f a recur = 1 + recur a？就像fix將f作爲參數一樣，Fix通過Cons作爲自身的參數。讓我們檢查的fix的定義和Fix並排側：

fix :: (p -> p) -> p 
fix f = f (fix f) 

-- Fix :: (* -> *) -> * 
newtype Fix f = Fix {nextFix :: f (Fix f)} 

如果忽略構造函數名的絨毛等，你會發現這些人基本上是完全相同的定義！

---

對於Toy數據類型的例子，一個可以只把它定義遞歸像這樣：

data Toy a = Output a (Toy a) | Bell (Toy a) | Done 

但是，我們可以使用Fix本身傳遞到本身，具有替代的Toy a所有實例第二種參數：

data ToyStep a recur = OutputS a recur | BellS recur | DoneS 

因此，我們可以使用Fix (ToyStep a)，這將相當於Toy a，儘管形式不同。事實上，讓我們證明他們是等價的：「爲什麼這樣做」

toyToStep :: Toy a -> Fix (ToyStep a) 
toyToStep (Output a next) = Fix (OutputS a (toyToStep next)) 
toyToStep (Bell next) = Fix (BellS (toyToStep next)) 
toyToStep Done = Fix DoneS 

stepToToy :: Fix (ToyStep a) -> Toy a 
stepToToy (Fix (OutputS a next)) = Output a (stepToToy next) 
stepToToy (Fix (BellS next)) = Bell (stepToToy next) 
stepToToy (Fix (DoneS)) = DoneS 

---

你可能會想，通常情況下，沒有太多的理由這樣做。然而，定義這些數據類型的簡化版本實際上可以讓你做出非常有表現力的功能。這裏有一個例子：

unwrap :: Functor f => (f k -> k) -> Fix f -> k 
unwrap f n = f (fmap (unwrap f) n) 

這真是一個令人難以置信的功能！當我第一次看到它時，它讓我感到吃驚！使用Cons數據類型，我們早些時候下面是一個例子，假設我們做了一個Functor實例：

getLength :: Cons a Int -> Int 
getLength Nil = 0 
getLength (Cons _ len) = len + 1 

length :: Fix (Cons a) -> Int 
length = unwrap getLength 

這基本上是fix爲免費的，因爲我們用我們使用任何數據類型Fix！

現在讓我們來想象一個功能，因爲ToyStep a是一個仿函數實例，簡單地收集所有OutputS s轉換列表，像這樣：

getOutputs :: ToyStep a [a] -> [a] 
getOutputs (OutputS a as) = a : as 
getOutputs (BellS as) = as 
getOutputs DoneS = [] 

outputs :: Fix (ToyStep a) -> [a] 
outputs = unwrap getOutputs 

這是使用Fix而不是你的力量自己的數據類型：一般性。