使用 Haskell 创建高阶函数

我最近一直在自学 Haskell，我的练习之一是实现一个接受两个参数的函数：一个列表和一个值。该函数将检查该值是否在列表中两次或更多次。我无法使用函数元素或成员。

我尝试删除不等于该值的值。然后检查新列表的大小，如果它大于 1，则输出True如果不是，则输出 False 。我在尝试使用函数内的函数时遇到问题。

remove2 val [] = []
remove2 val (x:xs) = if ( not (x == val))
                         then remove2 val xs 
                         else x:remove2 val xs
isMemberTwice :: (Eq val) => val -> [val] -> Bool 
isMemberTwice val [] = False
isMemberTwice val (x:xs) 
     | ( >= (length (remove2 val [val])) 2) = True
         | otherwise = a `isMemberTwice’` xs

高阶函数是将另一个函数作为参数或返回另一个函数的函数。

使用短递归函数可以轻松解决您手头的问题：

memtwice :: (Eq a) => a -> [a] -> Bool
memtwice value list = scan value list False
 where scan _ [] _ = False
       scan v (x:xs) True =
         if v == x then True
          else scan v xs True
       scan v (x:xs) False =
         scan v xs (v == x)

scan是一个将状态信息(是否已经找到一个实例(作为附加参数的函数。

可以使用更高阶的函数重写它，例如fold尽管我不确定如何实现短路行为(一旦找到两个实例就停止(。

列表中的每个函数都可以以以下形式编写：

f     [] = ...   -- also called the "base case"
f (a:as) = ...   -- also called the recursive case

让我们将这个想法应用于编写一个函数，该函数确定数字 3 至少出现在列表中一次：

hasA3 :: [Int] -> Bool
hasA3  []     = ...
hasA3  (a:as) = ...

显然hasA3 [] = False.我会让你弄清楚如何编写递归案例。提示：该函数可能必须检查 a == 3。

现在让我们编写一个函数来确定列表是否包含两个或多个 three。我们再次从两种情况开始：

hasTwo3s :: [Int] -> Bool
hasTwo3s []     = ...
hasTwo3s (a:as) = ...

同样，基本情况很容易。递归情况的提示：您可能需要检查 a == 3，然后您可能想要使用 hasA3 函数。

我将从

最后一点开始补充Daniel Jour的答案：

可以使用高阶函数(如fold 虽然我不确定如何实现短路然后的行为(一旦找到两个实例就停止(。

让我们转换原始代码：

memtwice value list = scan value list False
 where scan _ [] _ = False
       scan v (x:xs) True =
         if v == x then True
          else scan v xs True
       scan v (x:xs) False =
         scan v xs (v == x)

转到布尔运算符，我们得到：

memtwice value list = scan value list False
 where scan _ [] _ = False
       scan v (x:xs) True  = v == x || scan v xs True
       scan v (x:xs) False = scan v xs (v == x)

现在，参数v始终是value，所以让我们删除参数。

memtwice value list = scan list False
 where scan [] _ = False
       scan (x:xs) True  = value == x || scan xs True
       scan (x:xs) False = scan xs (value == x)

为最后一个参数引入显式 lambda(不是真正需要的，但有助于可读性(：

memtwice value list = scan list False
 where scan [] = (_ -> False)
       scan (x:xs) = found -> if found 
                                 then value == x || scan xs True
                                 else scan xs (value == x)

我们现在看到最后一个递归模式是一个foldr：事实上我们对scan []有一个基本情况定义，而递归情况scan (x:xs)仅根据scan xs来定义。

memtwice value list = foldr go (_ -> False) list False
 where go x next = found -> if found 
                                 then value == x || next True
                                 else next (value == x)

请注意，foldr似乎使用四个参数进行调用。这是因为go x next产生一个函数，因此foldr go (_ -> False) list也会产生函数。我们现在可以恢复显式 lambda。

memtwice value list = foldr go (_ -> False) list False
 where go x next True  = value == x || next True
       go x next False = next (value == x)

最后，请注意，由于||具有短路行为，我们确实实现了与原始代码等效foldr。

实际上有一种更简单的方法：

isMemberTwice needle haystack = n >= 2
  where n = length $ filter (== needle) haystack

但是，这种方法的缺点是，如果您向它传递一个很长的列表，它将评估整个列表，这是不必要的：您只需要查看是否至少出现 2 次needle。

因此，更好的解决方案是避免在过滤列表中使用length，而只使用模式匹配：如果它与(_:_:_)匹配，则必须至少出现 2 次：

isMemberTwice needle haystack = case occurrences of (_:_:_) -> True
                                                    _       -> False
  where occurrences = filter (== needle) haystack

相关内容

最新更新

热门标签：