將高階函數提升爲單目標

Question

比方說，我有一個高階函數，它使用從函數參數中檢索的值執行一些計算。

f :: a -> (b -> c) -> d 

其中a，b，C，d是一些具體的類型。

然後，我有一個功能與這種類型

g :: b -> m c 

其中m是一些單子。

現在有一種方法可以將f與f一起使用。那就是把f變成一個函數，產生m d而不是d，並且可以使用g作爲第二個參數？

一個具體的例子是m是IO monad，f是函數計算從其功能參數中檢索到的n個數字的和，g從標準輸入中讀取數字。

f n g = sum $ map g (1..n) 
g :: Int -> IO Int 
g _ = readLn 

我知道有對標準輸入轉換成一個懶惰的名單，這將解決這個問題，但我的實際情況並非如此簡單的功能。

假設我有一個在圖上做某事的算法。該算法使用功能參數來確定節點的鄰居。這樣我就可以有多個圖形的實現。

現在我想用一個非確定性圖（List monad）或未完全知道的圖（可能是monad）使用此算法。我知道我可以重寫算法來使用單子，然後使用monad作爲基本情況，但這是唯一的方法嗎？我認爲編寫沒有monad的算法會更容易。

這種行爲可行嗎？我無法找到它不應該的原因，但我無法找到如何去做的方法。

Answer 1

所以你想要從map得到mapM。這是你有一個簡單的map：

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

，你想用它作爲map on monadic structures

mapM :: Monad m => (a -> m b) -> [a] -> m [b] 

我們可以通過映射的IO操作，然後對其進行測序，從而計算從mapmapM：

mapM f xs = sequence (map f xs) 

現在我們有更一般的形式，我們可以通過運行0123找回 in the Identity monad.然後經典map是mapM中的身份monad。

> let g :: Int -> Identity Int 
     g a = return (a^2) 

其中：

> runIdentity $ mapM g [1..10] 
[1,4,9,16,25,36,49,64,81,100] 

所以，是的，你需要generlize您的高階功能，以正確的水平 - 是單子，或函子，或應用性，那麼你可以自由地替代其他計算概念，包括身份。

可以機械地重寫任何純函數的單子，由transformting的AST的功能：

• 包裹在return
• 識別新單子子表達式的結果值，並結合他們。
• 用monadic bind替換變量綁定;或者，如果是應用性：
• 與替換應用程序的單子應用（服用一些保健）

例如

map f []  = [] 
map f (x:xs) = f x : map f xs 

要（應用性風格）

mapM f []  = return [] 
mapM f (x:xs) = (:) <$> f x <*> mapM' f xs 

或不太清楚，並固定計算順序：

mapM f []  = return [] 
mapM f (x:xs) = do 
    v <- f x 
    vs <- mapM f xs 
    return (v:vs) 

我們可以使用applicatives在地圖，因爲沒有必要爲一元綁定以將結果從一步傳遞到下一步。 foldl：

foldl  :: (a -> b -> a) -> a -> [b] -> a 
foldl f z0 xs0 = lgo z0 xs0 
    where 
     lgo z []  = z 
     lgo z (x:xs) = lgo (f z x) xs 

foldlM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a 
foldlM f z0 xs0 = lgo z0 xs0 
    where 
     lgo z []  = return z 
     lgo z (x:xs) = do 
      v <- f z x 
      lgo v xs