Haskell/解決方案/高階函式

選擇比較方式

練習
編寫`insensitive`，使得`quickSort insensitive dictionary`給出`["a", "for", "have", "I", "Linux", "thing"]`

import Data.Char (toUpper)
insensitive string1 string2 = compare (map toUpper string1) (map toUpper string2)

與其直接比較兩個字串，我們比較兩個字串的全大寫版本。然後，根據大寫版本的順序確定原始兩個字串的順序。

高階函式和型別

練習

（有挑戰性） 下面的練習結合了你對高階函式、遞迴和 I/O 的學習。我們將重新建立在命令式語言中被稱為for 迴圈的東西。實現一個函式

for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO ()
for i p f job = -- ???

這個函式使用方式的一個例子可能是

for 1 (<10) (+1) print

它在螢幕上列印數字 1 到 9。

for 的預期行為是：從初始值i開始，for 首先檢查p i，如果它評估為真，那麼它執行job i，否則它停止並且不執行任何操作。如果執行了job i，那麼它使用f 修改這個值並檢查修改後的值f i 是否滿足某個條件p。如果不滿足，它停止；否則，for 迴圈繼續，使用修改後的f i 代替i。

在 Haskell 中實現 for 迴圈。
上面的段落給出了 for 迴圈的命令式描述。用更函式式的術語描述你的實現。

你可以嘗試一些更具挑戰性的練習

考慮一個像“列印從 1 到 10 的數字列表”這樣的任務。鑑於print 是一個函式，並且我們想要將它應用於一個數字列表，使用map 看起來是自然的事情。但這真的有效嗎？
實現一個函式sequenceIO :: [IO a] -> IO [a]。給定一個操作列表，這個函式按順序執行每個操作並返回它們的結果作為列表。
實現一個函式mapIO :: (a -> IO b) -> [a] -> IO [b]，它給定一個型別為a -> IO b 的函式和一個型別為[a] 的列表，對列表中的每個專案執行該操作，並返回結果。

此練習的靈感來自 osfameron 的部落格文章。不要偷看！

第一部分

1. Haskell 中的 for 迴圈

for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO ()
for i p f job =
    if p i
    then do
      job i
      for (f i) p f job
    else return ()

*Main> for 0 (<3) (+1) (print)
0
1
2

2. for i p f job 是一個遞迴構建的IO 操作。在每個遞迴步驟的開始，檢查布林值p i。基本情況是在p i 為False 時到達，結果是不執行任何操作的操作return ()。在遞迴情況下，結果是一個操作，它由job i 接著for 組成，for 使用f i 而不是i 呼叫，並且具有與之前相同的函式引數。

第二部分

1. 天真的解決方案map print [1..10] 將不起作用。map print [1..10] 的型別是[IO String]，一個操作列表。就其本身而言，這沒有什麼錯，因為操作是 Haskell 值，就像其他值一樣。但是，操作列表不是操作，因此它不能（例如）被放到IO do 塊中並透過main 執行。

2.

sequenceIO :: [IO a] -> IO [a]
sequenceIO [] = return []
sequenceIO (a:as) = do
    v <- a              -- runs the first action; binds the result to v.
    vs <- sequenceIO as -- recursive call; binds the other results to vs.
    return (v : vs)     -- returns all results.

或者使用foldr

sequenceIO :: [IO a] -> IO [a]
sequenceIO = foldr (\a seqio -> do v  <- a
                                   vs <- seqio
                                   return (v:vs))
                   (return [])

3.

mapIO :: (a -> IO b) -> [a] -> IO [b]
mapIO f [] = return []
mapIO f (x:xs) = do
    y <- f x
    ys <- mapIO f xs
    return (y : ys)

或者，可以根據sequenceIO 實現mapIO

mapIO :: (a -> IO b) -> [a] -> IO [b]
mapIO f xs = sequenceIO (map f xs)

或者無點式

mapIO :: (a -> IO b) -> [a] -> IO [b]
mapIO f = sequenceIO . map f

函式操作

練習

編寫curry、uncurry 和const 的實現。
在不測試它們的情況下描述以下函式的作用
- uncurry const
- curry fst
- curry swap，其中swap :: (a, b) -> (b, a) 交換一對元素。（swap 可以在Data.Tuple 中找到。）
（非常難） 使用foldr 實現foldl。提示：首先回顧列表 III 中關於foldr 和foldl 的部分。有兩個解決方案；一個是相對無聊的，另一個是真正有趣的。對於有趣的一個，仔細考慮一下如何組合一個列表中的所有函式。

1.

myUncurry :: (a -> b -> c) -> (a, b) -> c
myUncurry f (x, y) = f x y

myCurry :: ((a, b) -> c) -> a -> b -> c
myCurry f x y = f (x, y)

myConst :: a -> b -> a
myConst x _ = x

一種風格上的替代方案是使用 lambda 來強調正在返回一個函式。如果你在嘗試實現一個返回函式的函式時感到困惑，那麼這樣做可能會讓你更容易看到實現應該是什麼樣子。

myUncurry :: (a -> b -> c) -> ((a, b) -> c)
myUncurry f = \(x, y) -> f x y

myCurry :: ((a, b) -> c) -> (a -> b -> c)
myCurry f = \x y -> f (x, y)

myConst :: a -> (b -> a)
myConst x = \_ -> x

2.

uncurry const 按順序將一對的元素傳遞給const。由於const 總是返回它的第一個引數，因此uncurry const 返回一對的第一個元素；換句話說，它是fst 的偽裝。
curry fst 將fst 轉換為一個有兩個引數的函式，它返回第一個引數；因此，curry fst 等效於const。
或者，curry 和uncurry 是逆函式（也就是說，它們互相撤銷；curry . uncurry 等同於id），因此如果uncurry const 是fst，那麼很明顯curry fst 是const。

第三種方法是注意到，給定curry 和fst 的型別，curry fst 的型別是一個a -> b -> a 函式。唯一具有此型別的函式是const；因此，curry fst 必須等效於它。
swap 給定一對，產生一對，其中元素被交換。因此，curry swap 接受兩個引數，並將它們按交換的順序配對；它等效於flip (,)。

所有上述答案都可以透過展開和替換定義來嚴格檢查。以下是第一種情況的執行方式；我們建議你用其他兩種方式嘗試一下。

-- For the sake of mind-numbing explicitness, we will expand all
-- definitions as functions of a single argument, using nested lambdas.
uncurry const
(\f -> \(x, y) -> f x y) const -- Definition of uncurry.
\(x, y) -> const x y           -- Applying to const.
\(x, y) -> (\x -> \_ -> x) x y -- Definition of const.
\(x, y) -> (\_ -> x) y         -- Applying to x.
\(x, y) -> x                   -- Applying to y.

3. 以下是細緻入微的逐步解釋。如果你在這裡是因為你放棄了練習，你仍然可以跳到最後，嘗試理解實現的作用，然後再返回並檢視它是如何構建的。

要完成這個技巧，需要兩個關鍵的見解。第一個是記住左摺疊

foldl f acc xs
-- To make things easier to see, we will make xs = [a, b, c]
-- wherever we need a concrete example. 
foldl f acc [a, b, c]

可以擴充套件為

f (f (f acc a) b) c

然後意識到如果我們翻轉f 並交換它的所有引數

flip f c (flip f b (flip f a acc)))

我們得到一個表示式，它與右摺疊一樣關聯到右邊！

foldr g acc [x, y, z]
-- can be expanded as
g x (g y (g z acc)))
-- Now make g = flip f; x = c; y = b and z = a.

唯一的問題是我們右關聯表示式中的列表元素順序不對。修復它的明顯方法是反轉輸入列表。這導致了第一個解決方案

boringFoldl :: (b -> a -> b) -> b -> [a] -> b
boringFoldl f acc = foldr (flip f) acc . reverse

但是，反轉列表相當不優雅，並且需要與列表長度成正比的時間。在這一點上，第二個見解發揮作用。透過檢視包含巢狀flip f 的表示式，並眯著眼睛看一看

flip f c (flip f b (flip f a acc)))

我們可以看到我們實際上是在獲取acc，並依次應用多個函式。我們可以透過使用(.) 重寫表示式來使其透明。

flip f c . flip f b . flip f a $ acc

如果我們將(.) 切換到字首表示法

(.) (flip f c) ((.) (flip f b) (flip f a)) $ acc

很明顯，$ 左邊的函式可以用(.) 作為摺疊來寫

foldr (.) id [flip f c, flip f b, flip f a] $ acc

另一種思考這個步驟的方法是恢復對foldr 的直覺，它獲取一個列表，用二元運算子替換(:)，用初始累加器替換[]。在我們的例子中，id，即不做任何事情的啞函式，用作初始累加器。接下來，我們使用map 提取重複的flip f

foldr (.) id (map (flip f) [c, b, a]) $ acc

在這裡我們遇到了同樣的問題：列表元素的順序與我們希望的順序不同。反轉與函式與(.) 組合的事實一致，即函式從右到左應用。但是，這次我們可以簡單地翻轉(.)，而不是反轉列表

foldr (flip (.)) id (map (flip f) [a, b, c]) $ acc

僅僅翻轉折疊運算子不足以將foldr 轉換為foldl，因為在一般情況下，運算子引數具有不同的型別，因此翻轉會導致不匹配。但是，用(.) 摺疊一個列表只有在列表元素是a -> a 函式時才能起作用，並且a -> a 函式可以在兩個方向上組合。

透過從具體示例中抽象出來，我們得到了第二個解決方案

coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc xs = foldr (flip (.)) id (map (flip f) xs) acc

如果你發現這個最終表示式很難理解，那麼透過刪除flip 來使其更有指向性可能會有所幫助

coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc xs = foldr (\g h -> h . g) id (map step xs) acc
    where
    step x = \acc -> f acc x

或者，我們可以使其更無點式，儘管這會有點過分。

coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc = ($ acc) . foldr (flip (.)) id . map (flip f)