谓词和列表搜索 haskell

Question

我目前正在学习 Haskell，但有点停滞不前。我正在尝试编写一个函数，它接受一个谓词 p 和一个列表 xs 和 returns 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）的方法是将其分解为操作管道。

使用 zip 将列表中的每个项目与其后面的元素配对，因此我们有一个 (element, next) 对的列表。
使用 filter 删除 element 未通过谓词的对。
使用 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 擅长处理列表：当使用优化进行编译时，两种方法应该产生大致相同的机器代码——也就是说，高级解决方案没有性能成本

Answer 2

根据您的操作，您的代码出现了一些奇怪的地方：

map head [ys] 非常奇怪，它会导致您的函数停止：在匹配谓词的第一个元素处，您的函数 return 是一个包含其直接后继的列表并在那里停止。您仍然需要处理列表的其余部分。

此外，根据您对问题的定义，作为传递谓词的项的后继项的每个项都应该在结果数组中。我可能是错的，但我的理解是 afterFilter (<0) [-1, -1, 1] 应该 return [-1, 1].

但是，您通过调用 tail ys 丢弃了一个您没有检查的元素：您检查了 y，但没有检查 head ys。

最后，通过添加边缘情况，您将得到以下结果：

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

afterFilter _ [] = []
afterFilter _ [_] = []
afterFilter x (y:ys@(z:zs)) =
    if x y
        then z : afterFilter x ys
    else
        afterFilter x ys

Answer 3

尝试：

afterFilter :: (a -> Bool) -> [a] -> [a]
afterFilter p [] = []
afterFilter p [_] = []
afterFilter p (x1:x2:xs) 
  | p x1 = x2:rest
  | otherwise = rest
  where rest = afterFilter p (x2:xs)

或者

afterFilter' :: (a -> Bool) -> [a] -> [a]
afterFilter' p xs = map snd $ filter (\(x, _) -> p x) $ zip xs (tail xs)

或者

afterFilter'' :: (a -> Bool) -> [a] -> [a]
afterFilter'' p xs = [y | (x, y) <- zip xs (tail xs), p x]

谓词和列表搜索 haskell

predicate and a list search haskell

haskell

predicate

list