首页 文章

用case表达式Haskell递归

提问于
浏览 次
-4

请考虑以下代码，其中函数 sumFood 获取 Food 的列表 xs 并返回整数元组 . 在这个元组中，第一个整数表示 xs 中包含的水果数，第二个整数表示蔬菜数 .

module Apples where

data Food = Apple | Orange | Carrot | Potato  deriving(Show)

sumFood :: [Food] -> (Int, Int)

 sumFood (x:xs) = let v=0
                      f=0  in if ((length xs)-1) > 0  then
    case x of  Apple -> (f + 1, v)
               Orange -> (f + 1, v)
               Carrot -> (f, v + 1)
               Potato -> (f, v + 1)
                                 else sumFood xs

但如果我输入 sumFood [Apple , Orange] 或 [Apple, Apple] ，它将返回（0,0），答案应为（2,0） .

实现必须使用case表达式 .

也许一个提示会很有用 .

haskell

2 回答

  • 1

    (,) 的 Bifunctor 实例使这很容易;它允许您使用 first 和 second 将 (+1) 应用于元组的相应元素，这允许您简单地将列表折叠为元组 .

    import Data.Bifunctor

sumFood :: [Food] -> (Int, Int)
sumFood = foldr foo (0,0)
  where foo Apple = first (+1)
        foo Orange = first (+1)
        foo Carrot = second (+1)
        foo Potato = second (+1)

    如果您需要使用 case 表达式，请注意，定义函数的多个方程只是一个语法糖：

    sumFood :: [Food] -> (Int, Int)
sumFood = foldr foo (0,0)
  where foo food = case food of
                     Apple -> first (+1)
                     Orange -> first (+1)
                     Carrot -> second (+1)
                     Potato -> second (+1)

    如果您也不允许使用 Bifunctor ，那么您可以轻松实现自己：

    sumFood :: [Food] -> (Int, Int)
sumFood = foldr foo (0,0)
  where foo food = case food of
                     Apple -> \(f,v) -> (f+1,v)
                     Orange -> \(f,v) -> (f+1,v)
                     Carrot -> \(f,v) -> (f,v+1)
                     Potato -> \(f,v) -> (f,v+1)
    回复于
  • 3

    你实际上得到了大部分正确的点点滴滴，但顺序错误 - 你忘了对递归的结果做任何事情 .

    您可以替换 f 和 v 的值，看看发生了什么：

    sumFood (x:xs) = let v = 0
                     f = 0  in 
    if ((length xs)-1) > 0  then
        case x of  Apple -> (f + 1, v)
                   Orange -> (f + 1, v)
                   Carrot -> (f, v + 1)
                   Potato -> (f, v + 1)
    else sumFood xs

    变

    sumFood (x:xs) = 
    if ((length xs)-1) > 0  then
        case x of  Apple -> (0 + 1, 0)
                   Orange -> (0 + 1, 0)
                   Carrot -> (0, 0 + 1)
                   Potato -> (0, 0 + 1)
    else sumFood xs

    现在， ((length xs)-1) > 0 是 length xs > 1 ，这意味着 length (x:xs) > 2 ，所以在实践中你有

    • 如果列表包含两个以上的元素，则结果为 (1,0) 或 (0,1) .

    • 否则，递归 .

    现在（希望）显而易见的是，结果只能是 (1,0) 或 (0,1) - 除非输入的元素少于三个，在这种情况下，最终会遇到模式匹配失败 .

    主要问题是你从不使用递归的结果，因此结果始终是你的基本情况的结果 .

    首先，一个有用的经验法则是永远不要使用 length ;在列表结构上使用模式匹配 .

    从基本案例开始：空列表既不包含水果也不包含蔬菜 .

    sumFood [] = (0,0)

    接下来，您需要从递归中获取结果，然后将一个添加到结果的相应元素：

    sumFood (x:xs) = let (f, v) = sumFood xs 
                 in
                    case x of Apple -> (f + 1, v)
                   ...
    回复于

相关问题