我遇到了一個haskell問題。這是問題。
toList $ fromList [( ),(*)] <*> fromList [1..3] <*> fromList [10,100,1000] =
[11,101,1001,12,102,1002,13,103,1003,10,100,1000,20,200,2000,30,300,3000]
toList是一個將Tree型別轉換為list和fromList將 a 轉換list為TreeType的函式。
而我的作業是實作Applicative Class的pure和<*>運算子。這是我的工具。
data Tree a = Branch (Tree a) (Tree a) | Leaf a deriving (Eq, Show)
instance Applicative Tree where
pure = Leaf
Leaf f <*> t = f <$> t
Branch t1 t2 <*> Leaf a = t1 <*> Leaf a
Branch t1 t2 <*> Branch t3 t4 = Branch (t1 <*> t3) (t2 <*> t4)
但我不知道如何找出“所有組合”。請幫我。
uj5u.com熱心網友回復：
你對pure.
至于<*>，您也從Leaf f <*> t子句開始。跟著它走，一步一個腳印。例如：
data Tree a = Branch (Tree a) (Tree a) | Leaf a deriving (Eq, Show)
instance Functor Tree where
fmap f (Leaf a) = Leaf (f a)
fmap f (Branch l r) = Branch (fmap f l) (fmap f r)
instance Applicative Tree where
pure x = Leaf x
--
Leaf f <*> t = f <$> t
t <*> Leaf a = ($ a) <$> …
Branch l r <*> t = Branch (… <*> t) (r <*> …)
在撰寫代碼之前，您不必在腦海中想出完整的解決方案。只需開始逐句撰寫它，列舉您能想到的所有可能性（意思是每個引數的結構可能性——在這種情況下，無論是葉子還是分支）。您以后可以隨時洗掉多余的子句。
上面定義的<*>作品是遞回的。遞回的作業原理是假設我們已經對更簡單的情況有了定義，因此我們可以從更簡單的子部分的解決方案中為更復雜的情況構建結果。確保如果子問題的解決方案是正確的——并且根據假設它們是正確的——我們將這些部分解決方案正確組合，以便組合解決方案對整個問題是正確的：
recursion (problem) = solution where
problem has part1, part2, ...
sol1 = recursion(part1)
sol2 = recursion(part2)
....
solution is sol1, sol2, ..., combined properly together
所以在我們的例子中，什么時候tree1是Branch l r，
tree1 <*> tree2 =
case tree1 of Branch l r ->
let sol1 = l <*> tree2
sol2 = .....
in
combineTogether sol1 sol2
where
combineTogether subtree1 subtree2 = .....
只需完成它并在 REPL 上試用即可。通過遞回的魔力，看到它自己作業，因為我們還定義了如何直接處理最簡單的情況：
....
case tree1 of Leaf f ->
....
（將上述內容視為偽語法的位）。
因此，我們提出的定義的最后一行，
Branch l r <*> t = Branch (… <*> t) (r <*> …)
內容如下：一棵樹它是所有組合Branch l r，與另一棵樹t，是一個新的樹，這就是Branch new_l new_r，在這里new_l舉行的所有組合....用t，以及其他一，new_r持有其他組合（只是繼續前進，使那里最明顯的點替換）。
就像使用串列，在這里的所有組合[(1 ),(2 )]用[30,40]是結合了所有組合的串列[(1 )]與[30,40]的所有組合，并[(2 )]用[30,40]：
[(1 ),(2 )] <*> [30,40]
=
([(1 )] [(2 )]) <*> [30,40]
=
([(1 )] <*> [30,40]) ([(2 )] <*> [30,40])
uj5u.com熱心網友回復：
一種方法是注意葉樹是單子。
import Control.Monad (liftM2)
import Control.Applicative (Applicative (..))
instance Monad Tree where
Leaf a >>= f = f a
Branch l r >>= f = Branch (l >>= f) (r >>= f)
instance Applicative Tree where
pure = Leaf
liftA2 = liftM2
身份法 ( pure a >>= f = f a, m >>= pure = m):
pure a >>= f = Leaf a >>= f = f a
m >>= pure
-- Leaf case
Leaf a >>= pure
= -- def of >>=
pure a
= -- def of pure
Leaf a
-- Branch case
Branch l r >>= pure
= -- def of >>=
Branch (l >>= pure) (r >>= pure)
= -- structural induction
Branch l r
結合律 ( ((m >>= f) >>= g) = (m >>= (f >=> g))) :
(m >>= f) >>= g
-- when m = Leaf a
(Leaf a >>= f) >>= g
= --def of >>=
f a >>= g
= -- beta abstraction
(\q -> f q >>= g) a
= -- def of >>=
Leaf a >>= (\q -> f q >>= g)
= -- assumption
m >>= (\q -> f q >>= g)
-- when m = Branch l r
(Branch l r >>= f) >>= g
= -- def of >>=
Branch (l >>= f) (r >>= f) >>= g
= -- def of >>=
Branch ((l >>= f) >>= g) ((r >>= f) >>= g)
= -- Structural induction
Branch (l >>= (\q -> f q >>= g)) (r >>= (\q -> f q >>= g))
= -- def of >>=
Branch l r >>= (\q -> f q >>= g)
= -- assumption
m >>= (\q -> f q >>= g)
為了避免某些（通常很小）空間泄漏，您可以更改>>=位的定義，以便它可以行內：
instance Monad Tree where
m >>= f = go m
where
go (Leaf a) = f a
go (Branch l r) = Branch (go l) (go r)
因此應用組合是
fs <*> xs
= -- (<*>) = ap and the def of ap
do { f <- fs
; x <- xs
; return (f x)
}
= -- do notation rewrite
fs >>= (\ f -> xs >>= (\ x -> pure (f x)))
= -- re-write in terms of Leaf and Branch
-- with explicit case clauses
case fs of
Leaf f -> ...
Branch fl fr -> ...
從而得出定義。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/363875.html
標籤：哈斯克尔