list - 谓词和列表搜索haskell

Question

我目前正在学习 Haskell，但有点停滞不前。我正在尝试编写一个带有谓词 p 的函数和一个列表 xs并返回 xs 的那些元素的列表它紧跟在传递谓词 p 的元素之后.这是我所拥有的:

afterFilter :: (a -> Bool) -> [a] -> [a]

afterFilter x (y:ys) =

    if x y

        then (map head [ys])

    else

        afterFilter x (tail ys) 

测试输入:afterFilter (<0) [-4,7,-4,-8,3,-3,-6,0,-9,-1]

输出:[7]

Answer 1

诀窍是通过模式匹配两个 cons 单元从输入列表中拉出 两个 元素。如果第一个元素通过谓词，我们将第二个元素贴在输出上。但是在进行递归调用时，不要忘记将第二个元素粘贴回输入列表。

afterFilter :: (a -> Bool) -> [a] -> [a]
afterFilter f [] = []   -- input list is empty
afterFilter f [x] = []  -- input list has only one element - no "next element" to return
afterFilter f (x:y:xs) =
    let ys = afterFilter f (y:xs)
    in (if f x then y:ys else rest)

但是，解决该问题的更高级别(更 Haskellish)的方法是将其分解为操作管道。

1. 使用 zip 将列表中的每个项目与它后面的元素配对，因此我们有一个 (element, next) 对列表。
2. 使用 filter 删除 element 未通过谓词的对。
3. 使用 map 提取每个幸存对的 next 部分。

所以代码看起来是这样的:

pairWithSuccessors :: [a] -> [(a, a)]
pairWithSuccessors xs = zip xs (tail xs)

afterFilter :: (a -> Bool) -> [a] -> [a]
afterFilter p xs =
    let withSuccessors = pairWithSuccessors xs (tail xs)
        filtered = filter (\(element, next) -> p element) withSuccessors
        filteredSuccessors = map (\(element, next) -> next) filtered
    in filteredSuccessors

或者，以无点风格编写:

afterFilter p = map snd . filter (p . fst) . pairWithSuccessors

使用组合运算符 . 构建的函数从右到左读取:首先是pairWithSuccessors，然后是filter (p . fst)，然后在结果上 map snd。

GHC 擅长处理列表:当使用优化进行编译时，两种方法应该产生大致相同的机器代码——也就是说，高级解决方案没有性能成本