每当我阅读 Monad 示例时，他们总是将 IO 作为案例研究。
有没有人可以提出的单子进行列表操作的例子？我认为这可能有点矫枉过正，但如果 monad 能够比常规列表操作技术更具优势，我很感兴趣。
问问题
540 次
6 回答
9
Haskell 中 list monad 的一大秘密是，列表推导是do 块的语法糖。任何时候你写一个列表推导式，你都可以用一个 do 块来代替它，它使用 list monad 实例。
一个简单的例子
假设您要获取两个列表，并返回它们的笛卡尔积（即第一个列表和第二个列表(x,y)的每个组合的列表）。xy
您可以通过列表理解来做到这一点：
ghci> [(x,y) | x <- [1,2], y <- [3,4]] -- [(1,3),(1,4),(2,3),(2,4)]
列表理解是这个 do 块的语法糖：
zs = do x <- [1,2]
y <- [3,4]
return (x,y)
这反过来又是语法糖
zs = [1,2] >>= \x -> [3,4] >>= \y -> return (x,y)
一个更复杂的例子
但是，该示例并没有真正展示 monad 的强大功能，因为您可以轻松编写它，而无需依赖列表具有 Monad 实例的事实。例如，如果我们只使用 Applicative 实例：
ghci> import Control.Applicative
ghci> (,) <$> [1,2] <*> [3,4] -- [(1,3),(1,4),(2,3),(2,4)]
现在假设您获取正整数列表中的每个元素，并将其复制多次（例如f [1,2,3] = [1,2,2,3,3,3]，例如）。谁知道你为什么要这样做，但这很容易：
ghci> let f xs = [ y | x <- xs, y <- replicate x x ]
ghci> f [1,2,3] -- [1,2,2,3,3,3]
这只是语法糖：
f xs = do x <- xs
y <- replicate x x
return y
这反过来又是语法糖
f xs = xs >>= \x -> replicate x x >>= \y -> return y
这次我们不能只使用应用程序实例来编写它。关键区别在于我们从第一个绑定 ( x) 中获取输出，并使块的其余部分依赖于它 ( y <- replicate x x)。
于 2012-10-03T11:41:54.007 回答
9
使用 list monad 巧妙地编写“简单”列表实用函数的经典示例是：
import Control.Monad (filterM)
-- | Compute all subsets of the elements of a list.
powerSet :: [a] -> [[a]]
powerSet = filterM (\x -> [True, False])
的类型filterM是Monad m => (a -> m Bool) -> [a] -> m [a]。在 list monad 的上下文中，这是一个非确定性列表过滤器：一个过滤器操作，它采用一个返回替代答案列表的非确定性谓词。的结果又是替代可能结果的列表。filterM
或者用更简单的语言，filterM (\x -> [True, False])意味着：对于列表的每个元素，我都希望保留它并丢弃它。 filterM找出对每个列表元素执行此操作的所有可能组合。
于 2012-10-03T16:54:17.177 回答
4
这是为给定整数查找除数对的一种非常愚蠢的方法：
divisors:: Int -> [(Int,Int)]
divisors n = do
x <- [1 .. n]
y <- [1 .. n]
if x*y == n then return (x, y) else []
这个片段的意思应该是相当直截了当的。显然，这是解决这个特定问题的愚蠢方法。（在这种情况下可能有更有效的方法。）但是现在想象一些更复杂的问题，其中这个搜索非常复杂。这种用于搜索的成语可能非常有用。
于 2012-10-03T15:51:20.153 回答
3
另一个例子是从它的素数分解构造一个数字的所有除数（尽管是无序的）：
divs n = map product
. mapM (\(p,n)-> map (p^) [0..n])
. primeFactorization $ n
-- mapM f = sequence . map f
-- primeFactorization 12 ==> [(2,2),(3,1)] -- 12 == 2^2 * 3^1
函数finmapM f == sequence . map f为输入列表中的每个条目生成一个因子的幂列表；然后sequence形成通过列表的所有路径，一次从每个列表中选择一个数字；然后将所有可能组合的列表提供给map product它计算除数：
12 -- primeFactorization:
[(2,2),(3,1)] -- map (\(p,n)-> ...):
[ [1,2,4], [1,3] ] -- sequence:
[[1,1],[1,3],[2,1],[2,3],[4,1],[4,3]] -- map product:
[1,3,2,6,4,12] -- the divisors of 12
Luis Casillas 的回答中给出的精彩描述也适用于这里：
在 list monad 的上下文中，
mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]是一个nondeterministic list map：映射一个非确定性函数的映射操作 - 这样产生一个替代结果的列表 - 在一个列表上，创建所有替代的可能结果列表。
于 2012-10-04T00:09:17.273 回答
3
列表操作的一个很好的例子是查询 HTML/XML 文档，例如jQuery。jQuery 是一个单子。让我们看一个例子：
$(doc).find('> body')
.find('> *')
.is('table')
.is('.bar')
.find('> caption')
.text()
这为您提供了所有具有 CSS 类的顶级表的标题bar。这是使用 jQuery 的一种不同寻常的方式（通常您只需这样做body > table.bar > caption），但那是因为我想展示这些步骤。
在xml-conduit你做同样的事情：
child cursor >>= element "body" >>= child
>>= element "table" >=> attributeIs "class" "bar"
>>= child >>= element "caption"
>>= descendants >>= content
list monad 所做的是结合这些步骤。monad 本身对 HTML/XML 一无所知。
在HXT您以几乎相同的方式进行操作。较新HXT的版本使用所谓的箭头而不是单子，但基本原理是相同的。
于 2012-10-04T12:41:21.477 回答
2
guard当与ofMonadPlus或者另一个 monad结合使用时，Monad 和列表操作会更加有趣。举个例子，让我们解决经典的口头算术难题：SEND + MORE = MONEY. 每个字母必须代表一个唯一的数字，并且前导数字不能为零。
为此，我们将从StateTand构造一个 monad 堆栈[]：
import Control.Monad
import Control.Monad.List
import Control.Monad.State
-- Verbal Arithmetic monad
type VA a = StateT [Int] [] a
单子列表允许我们分支计算以搜索所有可能的方式，状态是可供选择的数字列表。我们可以通过给它所有可能的数字来运行这个 monad：
runVA :: VA a -> [a]
runVA k = evalStateT k [0..9]
我们需要一个辅助函数，它通过选择所有可用的数字来分支计算，并用剩余的数字更新状态：
pick :: VA Int
pick = do
-- Get available digits:
digits <- get
-- Pick one and update the state with what's left.
(d, ds) <- lift $ split digits
put ds
-- Return the picked one.
return d
where
-- List all possible ways how to remove an element from a list.
split :: [a] -> [(a, [a])]
split = split' []
split' _ [] = []
split' ls (x:rs) = (x, ls ++ rs) : split' (x : ls) rs
此外，我们经常需要选择一个非零数字：
pickNZ :: VA Int
pickNZ = do
d <- pick
guard (d /= 0)
return d
现在解决这个难题很容易：我们可以简单地逐位实现加法，并检查guard结果的位数是否等于总和：
-- SEND
-- + MORE
-- ------
-- MONEY
money :: [(Int,Int,Int)]
money = runVA $ do
d <- pick
e <- pick
let (d1, r1) = (d + e) `divMod` 10
y <- pick
guard $ y == r1
n <- pick
r <- pick
let (d2, r2) = (n + r + d1) `divMod` 10
guard $ e == r2
o <- pick
let (d3, r3) = (e + o + d2) `divMod` 10
guard $ n == r3
s <- pickNZ
m <- pickNZ -- Actually M must be 1, but let's pretend we don't know it.
let (d4, r4) = (s + m + d3) `divMod` 10
guard $ r4 == o
guard $ d4 == m
return (ds [s,e,n,d], ds [m,o,r,e], ds [m,o,n,e,y])
where
-- Convert a list of digits into a number.
ds = foldl (\x y -> x * 10 + y) 0
这个谜题只有一个结果：(9567,1085,10652)。（当然代码可以进一步优化，但我希望它是简单的。）
更多谜题可以在这里找到：http: //www.primepuzzle.com/leeslatest/alphameticpuzzles.html。
于 2013-04-07T20:42:45.153 回答