Haskell中如何获取包含首个满足谓词元素的最短前缀？

要实现“获取列表中包含首个满足谓词p元素的最短前缀”，本质是取列表从开头到第一个符合p的元素（包含该元素）的部分。下面提供几种实用的实现方式：

方法1：递归实现（直观易懂） #

直接通过递归遍历列表，遇到第一个满足条件的元素时终止并返回前缀：

takeUntilFirst :: (a -> Bool) -> [a] -> [a]
takeUntilFirst _ [] = []
takeUntilFirst p (x:xs)
  | p x       = x : []  -- 找到首个满足条件的元素，返回包含它的前缀（含前面已遍历元素）
  | otherwise = x : takeUntilFirst p xs

示例：takeUntilFirst even [1,3,5,2,4] 返回 [1,3,5,2]

方法2：利用findIndex（简洁高效） #

借助Data.List中的findIndex找到首个满足条件元素的索引，再截取对应长度的前缀：

import Data.List (findIndex)

takeUntilFirst :: (a -> Bool) -> [a] -> [a]
takeUntilFirst p xs = case findIndex p xs of
  Nothing -> []  -- 无满足条件元素时返回空列表，可改为xs返回原列表
  Just i  -> take (i + 1) xs

注：findIndex p xs会返回首个满足p的元素的索引（Maybe Int类型），take (i+1)即可取到从开头到该元素的前缀。

方法3：利用span（最简洁的标准库方案） #

span会将列表拆分为“满足谓词的前缀”和“剩余部分”，我们反过来用span (not . p)拆分出所有不满足p的前缀，再拼接剩余部分的第一个元素：

takeUntilFirst :: (a -> Bool) -> [a] -> [a]
takeUntilFirst p xs = let (nonMatching, rest) = span (not . p) xs
                      in nonMatching ++ take 1 rest

• 如果列表中存在满足p的元素，rest非空，take 1 rest取到首个符合元素，拼接后就是目标前缀；
• 如果无满足元素，rest为空，最终返回nonMatching即原列表，若需返回空列表可修改为：

  takeUntilFirst p xs = let (nonMatching, rest) = span (not . p) xs
                        in if null rest then [] else nonMatching ++ take 1 rest
  

内容的提问来源于stack exchange，提问作者Brendan Langfield