下面是代碼。我對 applicative、functor、traversable 和 monad 有一定的了解。迭代器和產量型別，以及產量函式是我最難以理解的。例如，Iterator 中的 ior 和 Yield 中的 iora 是什么？traverseY 到底做了什么，簽名是什么意思？以及這里如何應用 Monad Cont 也讓我很困惑。感謝您的閱讀，任何輸入將不勝感激。
import Control.Monad.Cont
import Control.Monad.Random
import System.Random.Shuffle
data Iterator i o r =
Result r
| Susp o (i -> Iterator i o r)
--------------------------------------------------------------------------------------------
newtype Yield i o r a = Yield { unY :: Cont (Iterator i o r) a }
instance Functor (Yield i o r) where
fmap f (Yield m) = Yield (fmap f m)
instance Applicative (Yield i o r) where
pure a = Yield (pure a)
(Yield mf) <*> (Yield ma) = Yield (mf <*> ma)
instance Monad (Yield i o r) where
return a = Yield (return a)
(Yield m) >>= k = Yield (m >>= \a -> unY (k a))
instance MonadCont (Yield i o r) where
callCC c = Yield (callCC (\k -> unY (c (\a -> Yield (k a)))))
runYield :: Yield i o r r -> Iterator i o r
runYield (Yield m) = runCont m Result
yield :: o -> Yield i o r i
yield o = callCC (\k -> Yield (cont (\_ -> Susp o (\i -> runYield (k i)))))
-------------------------------------------------------------------------------------------
data Tree a = Empty | Node a (Tree a) (Tree a)
traverseY :: Tree a -> Yield (Tree a) (a,Tree a,Tree a) r ()
traverseY Empty = return ()
traverseY (Node a t1 t2) = do t <- yield (a, t1, t2); traverseY t
uj5u.com熱心網友回復：
AnIterator i o r表示一個程序，該程序重復獲取 type 的值i并輸出 type 的值o，最終i通過回傳 ar來中斷其中一個 s 之后的迭代。例如
accum :: Iterator Int Int Int
accum = go 0
where go n | n >= 100 = Result n
| otherwise = Susp n (\i -> go (n i))
-- potential usage
main :: IO ()
main = go accum -- iterator returns modified copies instead of mutating, so prepare to replace the iterator through iteration/recursion
where go (Result r) = putStrLn $ "Final total: " show r -- check whether iterator has values/extract values by pattern matching; a finished iterator can return extra data of type r if it likes
go (Susp o i) = do
putStrLn $ "Running total: " show o
putStr $ "Add: "
n <- readLn
go (i n) -- bidirectional communication! get "incremented" iterator by feeding in an input value (you could write no-input iterators by setting i = ())
是一個跟蹤某個累加器的迭代器n。它將每個輸入添加到累加器，每次輸出新的累加器。一旦累加器達到 100，它就會停止接受輸入并回傳最終值。請注意，由于一切都是不可變的，因此為了保持狀態，每次更改狀態時Iterator都必須回傳自身的新版本。依次迭代“通過”accum的人必須使用回傳的Iterator而不是accum自身。在 Python 中，你可以寫成accum：
def accum(): # calling accum() instead creates a new object that mutates itself through iteration
sum = 0
while sum < 100: sum = sum (yield sum)
return sum
# same usage
def main():
gen = accum()
o = next(gen)
try: # I was hoping the Python version would help understanding... but I think I overestimated how pythonic Python would be...
while True:
print(f"Running total: {o}")
o = gen.send(int(input("Add: ")))
except StopIteration as e:
print(f"Final total: {e.value}")
Yield i o r r被用作Iterator i o r. 您可以直接撰寫類似Yield的介面Iterator：
instance Functor (Iterator i o) where
fmap f (Result x) = Result (f x)
fmap f (Susp o i) = Susp o (fmap f . i)
instance Applicative (Iterator i o) where
pure = Result
liftA2 = liftM2
instance Monad (Iterator i o) where
Result r >>= f = f r
Susp o i >>= f = Susp o ((>>= f) . i)
-- yieldI x is the iterator that sends x to the caller and receives a value in return
-- in Python: def yieldI(x): return yield x
yieldI :: o -> Iterator i o i
yieldI x = Susp x Result
例如，您的 DFS 示例中的生成器是
data Tree a = Empty | Node a (Tree a) (Tree a)
dfsI :: Tree a -> Iterator b a (Tree b) -- yield elements of the tree (o = a) *and also* receive new elements to replace them (i = b), building a new tree (r = Tree b)
-- dfs = traverse yieldI
dfsI Empty = Result Empty
dfsI (Node l m r) = do
l' <- yieldI l
m' <- dfsI m
r' <- dfsI r
return (Node l' m' r')
The issue with using Iterator i o r directly here is that it is inefficient. (Remember that Haskell is lazily evaluated to understand the following.) If you "concatenate" many iterators, like ((x >>= f) >>= g) >>= h, then you run into trouble when you try to evaluate it. Say x evaluates to Susp o i. Then evaluating the bigger expression first does three function calls, into the >>=s, evaluates x to Susp o i, then creates new suspended function calls to produce Susp o (\a -> ((i a >>= f) >>= g) >>= h). When you iterate through this iterator (i.e. extract the lambda and call it with some argument), each iteration must walk through all the >>=s that are hanging on to the Iterator. Yikes. (Stated perhaps in more familiar terms, we've implemented iterator concatenation as a "wrapper" around another, which gets bad when you have wrappers on wrappers on wrappers...)
Using Cont is a "standard trick" for avoiding this. The idea is that, instead of handling an iterator x directly, we handle its bind function (wrapped in Cont and Yield newtypes) x' = \f -> x >>= f. Note that converting a monadic computation to its bind function is reversible, since x' return = x >>= return = x.
newtype Yield i o r a = Yield { unYield :: (a -> Iterator i o r) -> Iterator i o r }
instance Functor (Yield i o r) where
fmap f (Yield r) = Yield (\k -> r $ k . f)
instance Applicative (Yield i o r) where
pure x = Yield (\k -> k x)
liftA2 = liftM2
instance Monad (Yield i o r) where
Yield r >>= f = Yield (\k -> r $ \x -> unYield (f x) k)
-- newtype Yield i o r a = Yield { unYield :: (a -> Iterator i o r) -> Iterator i o r }
-- compare (>>=) :: Iterator i o a -> (a -> Iterator i o r) -> Iterator i o r
-- giving
liftIY :: Iterator i o a -> Yield i o r a
liftIY x = Yield (x >>=)
-- and the law x >>= return = x inspires
runYield :: Yield i o r r -> Iterator i o r
runYield (Yield r) = r return
-- e.g.
yield :: o -> Yield i o r i
-- yield = liftIY . yieldI
yield x = Yield (\k -> Susp x (\i -> k i)) -- note this is the same as yours after you drill through newtype baggage
Instead of having ((x >>= f) >>= g) >>= h, using Yield will make terms like (((x' >>= liftIY . f) >>= liftIY . g) >>= liftIY . h) return appear at runtime. This evaluates to just x' >>= _someFunction, so all the wrappers from before have collapsed into just one, hopefully leading to efficiency. (This collapsed wrapper will "replace itself" as you iterate through, going through the behaviors specified by f, g, and h in turn. This is encoded in Yield's >>=.)
-- magical free efficiency by replacing Iterator -> Yield, yieldI -> yield
dfs :: Tree a -> Yield b a r (Tree b)
dfs = traverse yield
-- when using Yields as builders, you will treat Yield i o _ r like Iterator i o r
-- the middle parameter should be polymorphic for builders like dfs
-- while the final consumer (particularly the "standard consumer" runYield) fixes it to something (runYield sets it to the final return type)
-- (this behavior is a loosely typed reflection of the Codensity monad)
At the final use site, Yields have to be made into Iterators before they can be iterated. Your dfsDirect:
- Uses
dfs = traverse yieldIto build aYieldwithout incurring the wrath of "accidentally quadratic left associativity" (technical term :)) - Builds an
Iteratorout of thatYieldusingrunYield. This iterator goes throughtrand yields/replaces its elements. - Iterates that iterator via
loop, which... - "Converses" with
dfsvia the lineloop (Susp o i) = loop (i [o]): when it receivesoit sends[o]back into the iterator, which puts it in theTreeit's building. - Upon exhausting the iterator, receives a new
Treewhere every element is replaced with a singleton list (loop (Result r) = _). - Concatenates all the lists together via the
Foldable Treeinstance.
This is a pretty dumb way to do things, since the order doesn't come from dfs but from the Foldable Tree instance used in the last step. The Iterator is just used as a glorified fmap function. If the Foldable instance were different (e.g. BFS, or even just inorder vs preorder), but you kept dfs as a preorder DFS (so it would no longer be written traverse yield), dfsDirect would not output in the actual order defined by dfs! You could write a function that properly turns an Iterator into a list.
-- note the usage of () as an input type for "plain" iterators
-- since we cannot know what to pass in otherwise
iToList :: Iterator () o r -> ([o], r)
iToList (Result r) = ([], r)
iToList (Susp o i) = (o : os, r)
where ~(os, r) = iToList (i ())
traverseY is also a bit strange. If it receives a Node (either as initial value or as an iterator input), it yields back the fields of the Node, and on Empty else it returns. It doesn't actually "traverse" its input; you can send it off into a completely new tree just by sending that tree as input. I assume the idea is that when you iterate over it, you send back one of the Trees it previously returned, so it iterates over a path to a leaf. IMO it would be nicer to write
data Direction = L | R
path :: Tree a -> Yield Direction a r () -- outputs root and goes in direction as told until it runs out of tree
path Empty = pure ()
path (Node x l r) = do
d <- yield x
case d of
L -> path l
R -> path r
-- potential use
elemBST :: Ord a => a -> Tree a -> Bool
elemBST x xs = go (runYield $ path xs)
where go (Result ()) = False -- iteration ended without success
go (Susp y i) = case compare x y of
LT -> go (i L) -- go left
EQ -> True -- end
GT -> go (i R) -- go right
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/450273.html
標籤：哈斯克尔