haskell - 将递归保护更改为高阶函数

Question

我正在尝试将基本函数转换为高阶函数(特别是 map、filter 或 foldr)。我想知道是否有任何简单的概念可以应用在我可以看到我使用 guard 编写的旧函数并将它们转换为更高阶的地方。

我正在修改一个名为 filterFirst 的函数从列表中删除不满足给定谓词函数(第一个参数)的第一个元素(第二个参数)。

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst _ [] = []
filterFirst x (y:ys)
    | x y       = y : filterFirst x ys
    | otherwise = ys

例如:

 greaterOne :: Num a=>Ord a=>a->Bool
 greaterOne x = x > 1

 filterFirst greaterOne [5,-6,-7,9,10]
 [5,-7,9,10]

基于基本递归，我想知道是否有办法将这个(和类似的函数)转换为更高阶的映射、过滤器或折叠器。我不是很先进，这些功能对我来说是新的。

Answer 1

首先，让我们翻转函数的参数顺序。这将使几个步骤更容易，我们可以在完成后将其翻转回来。 (我将其称为翻转版本 filterFirst' 。)

filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] _ = []
filterFirst' (y:ys) x
    | x y       = y : filterFirst' ys x
    | otherwise = ys

请注意 filterFirst' ys (const True) = ys为所有 ys .让我们替换它:

filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] _ = []
filterFirst' (y:ys) x
    | x y       = y : filterFirst' ys x
    | otherwise = filterFirst' ys (const True)

使用 if-else 代替守卫:

filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] _ = []
filterFirst' (y:ys) x = if x y then y : filterFirst' ys x else filterFirst' ys (const True)

将第二个参数移动到 lambda:

filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] = \_ -> []
filterFirst' (y:ys) = \x -> if x y then y : filterFirst' ys x else filterFirst' ys (const True)

现在我们可以把它变成 foldr .我们想要的模式是 filterFirst' (y:ys)可以用 filterFirst' ys 表示, 不使用 ys否则，我们现在就在那里。

filterFirst' :: Foldable t => t a -> (a -> Bool) -> [a]
filterFirst' = foldr (\y f -> \x -> if x y then y : f x else f (const True)) (\_ -> [])

现在我们只需要把它整理一下:

filterFirst' :: Foldable t => t a -> (a -> Bool) -> [a]
filterFirst' = foldr go (const [])
  where go y f x
          | x y       = y : f x
          | otherwise = f (const True)

并将论点翻转回来:

filterFirst :: Foldable t => (a -> Bool) -> t a -> [a]
filterFirst = flip $ foldr go (const [])
  where go y f x
          | x y       = y : f x
          | otherwise = f (const True)

我们完成了。 filterFirst根据 foldr 实现.

附录:虽然 filter不够强大，无法构建它， filterM与 State monad 一起使用时:

{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.State

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst x ys = evalState (filterM go ys) False
  where go y = do
          alreadyDropped <- get
          if alreadyDropped || x y then
            return True
          else do
            put True
            return False