Haskell如何实现基于指定函数求取列表最小元素的minBy函数

原代码存在的问题 #

• 类型签名完全不符合需求：
  1. 映射函数measure的类型错误，不是a -> Bool，而是需要将列表元素映射为可比较的值，类型为Ord b => a -> b
  2. 返回值类型错误，你需要返回列表中的元素，类型为a，而非固定类型Int
• 空列表处理逻辑错误：空列表不存在最小元素，返回0不仅类型不匹配，逻辑也不成立
• 模式匹配缺失：没有处理列表只有单个元素的边界情况
• 函数调用优先级错误：minBy measure x:rest会被编译器解析为(minBy measure x) : rest，完全不符合递归调用的预期，需要用括号包裹列表参数
• 比较逻辑错误：你需要保留measure计算结果更小的元素，而非更大的元素

正确实现 #

基础版本（和Prelude的minimum行为一致，空列表抛出异常） #

minBy :: Ord b => (a -> b) -> [a] -> a
minBy measure [] = error "minBy: empty list"
minBy measure [x] = x
minBy measure (x:xs) = 
  let minRest = minBy measure xs
  in if measure x < measure minRest then x else minRest

你也可以用Prelude的高阶函数简化实现：

minBy :: Ord b => (a -> b) -> [a] -> a
minBy measure = foldl1 (\acc cur -> if measure cur < measure acc then cur else acc)

安全版本（空列表返回Nothing，避免运行时异常） #

minBySafe :: Ord b => (a -> b) -> [a] -> Maybe a
minBySafe measure [] = Nothing
minBySafe measure (x:xs) = Just $ foldl (\acc cur -> if measure cur < measure acc then cur else acc) x xs

效果验证 #

-- 测试用例1：返回5
> minBy (\x -> -x) [1,2,3,4,5]
5

-- 测试用例2：返回"a"
> minBy length ["a", "abcd", "xx"]
"a"

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