Haskell/Solutions/列表 III

折叠

练习

以递归方式定义以下函数（类似于上面sum，product和concat的定义），然后将它们转换为折叠
- and :: [Bool] -> Bool，如果布尔值的列表全部为 True，则返回 True，否则返回 False。
- or :: [Bool] -> Bool，如果布尔值的列表中任何一个为 True，则返回 True，否则返回 False。
使用foldl1或foldr1定义以下函数
- maximum :: Ord a => [a] -> a，返回列表中的最大元素（提示：max :: Ord a => a -> a -> a返回两个值的较大者）。
- minimum :: Ord a => [a] -> a，返回列表中的最小元素（提示：min :: Ord a => a -> a -> a返回两个值的较小者）。
使用折叠（哪个？）来定义reverse :: [a] -> [a]，它返回一个元素顺序相反的列表。

请注意，所有这些都是 Prelude 函数，因此当你需要它们时，它们将始终近在咫尺。（另外，这意味着你将想要在 GHCi 中测试你的答案时使用略微不同的名称。）

and [] = True
and (x:xs) = x && and xs

--As a fold
and = foldr (&&) True

or [] = False
or (x:xs) = x || or xs

--As a fold
or = foldr (||) False

maximum :: Ord a => [a] -> a  -- omitting type declaration results in "Ambiguous type variable" error
maximum = foldr1 max --foldl1 also works, but not if you want infinite lists. Not that you can ever be sure of the maximum of an infinite list.
minimum :: Ord a => [a] -> a
minimum = foldr1 min --Same as above.

--Using foldl'; you will want to import Data.List in order to do the same.
reverse :: [a] -> [a]
reverse = foldl' flippedCons []
    where
    flippedCons xs x = x : xs

扫描

练习
编写你自己的`scanr`定义，首先使用递归，然后使用`foldr`。对`scanl`做同样的事情，首先使用递归，然后使用`foldl`。

-- with recursion
scanr2 step zero [] = [zero]
scanr2 step zero (x:xs) = step x (head prev):prev
  where prev = scanr2 step zero xs

scanl2 step zero [] = [zero]
scanl2 step zero (x:xs) = zero : scanl2 step (step zero x) xs

-- An alternative scanl with poorer performance. The problem is that
-- last and init, unlike head and tail, must run through the entire
-- list, and (++) does the same with its first argument.
scanl2Slow step zero [] = [zero]
scanl2Slow step zero xs = prev ++ [step (last prev) (last xs)]
  where prev = scanl2Slow step zero (init xs)

--with fold
scanr3 step zero xs = foldr step' [zero] xs
  where step' x xs = step x (head xs):xs

scanl3 step zero xs = (reverse . foldl step' [zero]) xs
  where step' xs x = step (head xs) x:xs

-- This implementation has poor performance due to (++), as explained
-- for scanl2Slow. In general, using (++) to append to a list
-- repeatdely is not a good idea.  
scanl3Slow step zero xs = foldl step' [zero] xs
  where step' xs x = xs ++ [step (last xs) x]

在上面高效的scanr实现中，我们使用head和tail来避免必须在 where 子句中分解列表参数并进行模式匹配，只是为了在右侧重新组装它。在模式匹配章节中，我们将看到 as 模式如何让我们在不需要head的情况下实现同样的效果。

练习

定义以下函数

factList :: Integer -> [Integer]，它返回一个从 1 到其参数的阶乘列表。例如，facList 4 = [1,2,6,24]。

更多内容待添加

factList n = scanl1 (*) [1..n]
factList' n = scanl (*) 1 [2..n]

过滤和列表推导

练习
编写一个`returnDivisible :: Int -> [Int] -> [Int]`函数，该函数过滤一个整数列表，只保留可以被第一个参数中传递的整数整除的数字。对于整数 x 和 n，如果`(mod x n) == 0`，则 x 可以被 n 整除（注意，偶数测试是这种情况的特例）。

returnDivisible :: Int -> [Int] -> [Int]
returnDivisible n xs = [ x | x<-xs , (mod x n) == 0 ]

--or, if you prefer to use filter...
returnDivisible :: Int -> [Int] -> [Int]
returnDivisible n = filter (\x -> (mod x n) == 0)

练习
使用列表推导语法和适当的保护（过滤器）编写一个`choosingTails :: [[Int]] -> [[Int]]`函数，对于空列表，返回一个在头部大于 5 之后尾部的列表 choosingTails [[7,6,3],[],[6,4,2],[9,4,3],[5,5,5]] -- [[6,3],[4,2],[4,3]] 保护的顺序重要吗？你可以通过使用前面练习的函数来找出答案。

choosingTails :: [[Int]] -> [[Int]]
choosingTails ls = [ tail l | l <- ls, not (null l), head l > 5 ]

列表推导中的布尔条件按顺序计算，因此如果你交换了条件，如下所示

choosingTails ls = [ tail l | l <- ls, head l > 5, not (null l) ]

如果其中一个l原来是一个空列表，程序将尝试对其应用 head，这会导致错误。首先放置not (null l)会导致程序在遇到空列表时，短路条件 - 也就是说，忽略第二个条件，因为第一个条件为假足以拒绝列表 - 因此避免执行 head [] 以及随之而来的错误。或者，你也可以通过模式匹配来过滤。只有非空列表才匹配(l:ll)，它被第一个元素l以及可能为空的尾部ll划分

choosingTails ls = [ ll | (l:ll) <- ls, l > 5 ]    -- filter by pattern match

练习
在这部分，我们已经看到列表推导本质上是`filter`和`map`的语法糖。现在反向操作，并使用列表推导语法定义`filter`和`map`的替代版本。

alternativeFilter :: (a -> Bool) -> [a] -> [a]
alternativeFilter cond xs = [ x | x<-xs, cond x ]

alternativeMap :: (a -> b) -> [a] -> [b]
alternativeMap f xs = [ f x | x<-xs ]
--no need for any condition, as all x will be accepted

练习
重写`doubleOfFirstForEvenSeconds`使用`filter`和`map`而不是列表推导。

doubleOfFirstForEvenSeconds' :: [(Int, Int)] -> [Int]
doubleOfFirstForEvenSeconds ps =
    let f pair = 2 * (fst pair)
        g pair = isEven (snd pair)
    in map f (filter g ps)

--isEven, naturally, remains the same.
isEven :: Int -> Bool
isEven n = (mod n 2 == 0)

doubleOfFirstForEvenSeconds' :: [(Int, Int)] -> [Int]
doubleOfFirstForEvenSeconds' ps = map ((2*) . fst) (filter (isEven . snd) ps)