1

任务：我正在尝试编写一个类型为 signature 的函数minimum_recursive :: (a -> a -> Bool) -> [a] -> a。对于它的第一个参数，它接受我将调用的带有less两个参数的函数，如果第一个参数小于第二个参数，则返回 True，否则返回 False。minimum_recursive也接受一个列表作为它的第二个参数。使用显式递归，minimum_recursive应该确定其输入列表 [a] 中的最小值。

我的想法：我想把实际的递归放在一个也接受累加器的辅助函数中。我会用第一项作为累加器来调用辅助函数。

到目前为止我有什么：到目前为止，我有以下内容：

-- function as first parameter to min'
-- accepts two params, returns True if
-- first must come before second in sorted
-- order
less :: Ord a => a -> a -> Bool
less a b = a < b

-- Subpart B
minimum_recursive :: (a -> a -> Bool) -> [a] -> a
minimum_recursive func list = minimum_recursive_h func list []

我什至不知道如何开始写作minimum_recursive_h。

注意：我知道可能有一种更简单的方法可以完成这项任务，但我需要按照上面的说明进行操作。

4

3 回答 3

2

你可以这样做：

minimum_recursive _ [] = error "no minimum of empty list"
minimum_recursive _ [x] = x
minimum_recursive f (x:xs) = let m = minimum_recursive f xs
                             in if f x m then x else m

或者，使用累加器：

minimum_recursive _ [] = error "no minimum of empty list"
minimum_recursive f (x:xs) = helper f x xs
    where
      helper _ m [] = m
      helper f m (x:xs) 
          | f m x = helper f m xs
          | otherwise = helper f x xs
于 2012-04-11T17:58:15.423 回答
1

如果您想要列表中的最小元素，我建议您将当前拥有的最小元素作为参数添加到函数中。

minimum_recursive :: (a -> a -> Bool) -> a -> [a] -> a
minimum_recursive f min [] = min
minimum_recursive f min (x:xs) | f min x   = minimum_recursive f min xs
                               | otherwise = minimum_recursive f x   xs

您还应该更改调用它的函数中的类型，a因为Maybe a在空列表中没有最小的元素。这里有一些关于Maybe的帮助

如果您想在没有额外参数的情况下执行此操作，您也可以将最小的元素存储在列表的开头。在这种情况下，使用 Maybe 很重要

minimum_recursive :: (a -> a -> Bool) -> [a] ->Maybe a
minimum_recursive f [] = Nothing
minimum_recursive f (x:[]) = Just x
minimum_recursive f (y:(x:xs)) | f y x     = minimum_recursive f (y:xs)
                               | otherwise = minimum_recursive f (x:xs)

这就是如何在折叠中找到最小值。看看函数式编程的美妙之处。但这不适用于空列表

simplefold :: [a] -> a
simplefold (x:xs) = foldl min x xs

但是我们可以将这个函数嵌入到一个检查列表是否为空并在这种情况下返回 Nothing 的函数中。

betterfold :: [a] -> Maybe a
betterfold [] = Nothing
beterfold l   = Just (simplefold l)
于 2012-04-11T17:44:48.510 回答
1

递归解决问题的经典方法如下：

  1. 假设你几乎解决了这个问题，除了最后一步。
  2. 编写代码，给定除最后一步之外的所有解决方案，计算最后一步产生的解决方案。
  3. 写出基本情况。

在列表的情况下，这转化为这种模式：

  1. 基本案例：解决方案应该是[]什么？（如果有的话；就您的minimum_recursive函数而言，这将是一个错误）。
  2. 对于非空列表x:xs，假设您已经拥有almostTheResult = minimum_recursive f xs. 鉴于此，您如何计算minimum_recursive (x:xs)？

我会给你一个很大的提示：你minimum_recursive可以用foldr这个函数来实现：

minBy :: (a -> a -> Bool) -> a -> a -> a
minBy pred x y = if pred x y then x else y

该foldr功能完全符合我上面描述的功能。的第一个参数foldr是计算给定列表头和尾的部分解的最终解的函数，第二个参数是结果基本情况。

于 2012-04-11T18:49:54.170 回答