Nested Mappings 案例的 Haskell 实现 - SICP § 2.2.3

问题

Problem: Given a positive integer $n$, find all ordered pairs of distinct positive integers $i$ and $j$, where $ 1 \leq i \leq j \leq n $, such that $ i + j $ is prime.

Haskell 实现

isDivisible :: Int -> Int -> Bool 
isDivisible x y 
    | mod x y == 0  = True 
    | otherwise     = False 

isPrime :: Int -> Bool
isPrime x 
    | x <= 2    = True 
    | otherwise = not (foldr (||) False (map (isDivisible x) [2..((floor . sqrt . fromIntegral) x)]))


genPairs :: Int -> [((Int, Int), Int)]
genPairs n = do 
    x <- [1..n]
    y <- [1..(x-1)]
    return ((y, x), (x + y))

sumPrimePairs :: Int -> [((Int, Int), Int)]
sumPrimePairs = (filter (\(_, s) -> (isPrime s))) . genPairs

关于 List Monad: Context, 嵌套 lambda 与 do-notation

Context of List Monad : 不确定的结果.

此章的标题是 Nested Mappings, 在代码层面的表现是嵌套的 lambda, Haskell 中的 do-notation 展开形式就是嵌套的 lambda, 前者是后者的语法糖.

此章中定义的 flatMap 就是 Haskell 中的 >>= (bind).

参考 Learn You a Haskell for Great Good 中的相关内容：A Fistful of Monads - the List Monad

List Monad 实现全排列

2024-08-30 补充： SICP page 168 集合全排列的 Haskell 实现

permutations :: Eq a => [a] -> [[a]]
permutations [] = [[]]
permutations xs = do
    x <- xs 
    perm <- permutations $ removeByElem x xs
    return (x: perm)

removeByElem :: Eq a => a -> [a] -> [a]
removeByElem x = filter (/= x)