haskell - 关于Haskell中的控制流结构(多个if-then-else)

Question

我想将以下程序程序转换为Haskell [用伪代码编写]:

f(x) {
  if(c1(x)) {
     if(c2(x)) {
        return a(x);
     }
     else if (c3(x)) {
      if(c4(x)) {
         return b(x);
     }
  }
  return d(x);
}

我编写了以下实现:

f x = 
  if (c1 x) then
     if(c2 x) then 
            a x
     else if (c3 x) then
              if (c4 x) then
                  b x
              else d x
     else d x
  else d x 

不幸的是，它包含(else d x)三次。

有没有更好的方法来实现该功能？ (即，如果不满足任何条件，则返回(d x)？)

我知道我们可以将条件c1和c2合并为(c1 x)&&(c2 x)以使if的数量更小，但是我的条件c1，c2，c3，c4确实很长，如果将它们组合起来，我将得到一种需要多条线的条件。

Answer 1

最简单，最明显的解决方案
如果您使用的是GHC，则可以打开

{-# LANGUAGE MultiWayIf #-}

而你的整个事情变成

f x = if | c1 x && c2 x         -> a x
         | c1 x && c3 x && c4 x -> b x
         | otherwise            -> d x

稍微先进和灵活的解决方案
但是，并非总是希望在Haskell中盲目复制命令性代码。通常，将代码视为数据很有用。您实际上所做的是设置 x必须满足的要求列表，然后，如果 x满足这些要求，则可以对 x采取一些措施。
我们可以用Haskell中的实际函数列表来表示这一点。看起来像

decisions :: [([a -> Bool], a -> b)]

decisions = [([c1, c2],     a)
            ,([c1, c3, c4], b)]
            ,([],           d)]

在这里，我们应将其读为:“如果 x同时满足 c1和 c2，则对 a采取 x措施”，依此类推。然后我们可以将 f定义为

f x = let maybeMatch = find (all ($ x) . fst) decisions
          match = fromMaybe (error "no match!") maybeMatch
          result = snd match
      in  result x

通过遍历需求列表并找到 x满足的第一组决策( maybeMatch)，可以工作。它将其从 Maybe中拉出(您可能希望在那里进行更好的错误处理!)然后选择相应的函数( result)，然后通过该函数运行 x。

非常先进且灵活的解决方案
如果您有一个非常复杂的决策树，则可能不想用一个平面列表来表示它。这是实际数据树派上用场的地方。您可以创建所需功能的树，然后搜索该树，直到您单击叶节点。在此示例中，该树可能看起来像

+-> c1 +-> c2 -> a
|      |
|      +-> c3 -> c4 -> b
+-> d

换句话说，如果 x满足 c1，它将查看它是否也满足 c2，并且是否对 a采取了 x Action 。如果不是，它将继续使用 c3进入下一个分支，依此类推，直到达到一个 Action (或遍历整个树)为止。
但是首先，您将需要一种数据类型来区分需求( c1， c2等)和操作( a， b等)之间的区别。

data Decision a b = Requirement (a -> Bool)
                  | Action (a -> b)

然后，您将决策树构建为

decisions =
  Node (Requirement (const True))
    [Node (Requirement c1)
       [Node (Requirement c2)
          [Node (Action a) []]
       ,Node (Requirement c3)
          [Node (Requirement c4)
             [Node (Action b) []]]
    ,Node (Action d) []]

这看起来比实际要复杂，因此您可能应该发明一种更简洁的表达决策树的方法。如果定义功能

iff = Node . Requirement
action = flip Node [] . Action

你可以把树写成

decisions =
  iff (const True) [
      iff (c1) [
          iff (c2) [
              action a
          ],
          iff (c3) [
              iff (c4) [
                  action b
              ]
          ]
      ],
      action d
  ]

突然之间，它与您开始使用的命令性代码非常相似，尽管事实是它是有效的Haskell代码，仅用于构建数据结构! Haskell在定义这样的自定义小“语言内部语言”方面非常强大。
然后，您需要在树中搜索可以达到的第一个 Action 。

decide :: a -> Tree (Decision a b) -> Maybe b

decide x (Node (Action f) _) = Just (f x)
decide x (Node (Requirement p) subtree)
  | p x       = asum $ map (decide x) subtree
  | otherwise = Nothing

这会使用一点Maybe魔术( asum)在第一次成功命中时停止。反过来，这意味着它不会徒劳地计算任何分支的条件(如果计算成本很高，这是有效且重要的)，并且它应该可以很好地处理无限决策树。
您可以充分利用 decide类，使 Alternative更加通用，但我选择将其专用于 Maybe，以便不撰写有关此书。使它变得更加笼统，也可以让您做出花哨的单子(monad)决策，这将非常酷!
但是，最后，作为此操作的一个非常简单的示例，请使用 Collatz conjecture。如果您给我一个数字，然后问我下一个数字应该是多少，我可以建立一个决策树来找出答案。该树可能如下所示:

collatz =
  iff (> 0) [
      iff (not . even) [
          action (\n -> 3*n + 1)
      ],
      action (`div` 2)
  ]

因此该数字必须大于0，然后将其乘以3，然后加1，否则将其减半。测试运行表明

λ> decide 3 collatz
Just 10
λ> decide 10 collatz
Just 5
λ> decide (-4) collatz
Nothing

您可能可以想象更多有趣的决策树。

大约一年后进行编辑:替代方法的推广实际上非常简单，也很有趣。 decide函数获得新外观

decide :: Alternative f => a -> Tree (Decision a b) -> f b

decide x (Node (Action f) _) = pure (f x)
decide x (Node (Requirement p) subtree)
  | p x       = asum $ map (decide x) subtree
  | otherwise = empty

(对于那些保持计数的状态，总共只有三个更改。)这为您提供了使用列表的适用实例而不是Maybe组合输入满足的“所有” Action 的机会。这揭示了我们的 collatz树中的“错误”-如果我们仔细查看，就会发现它说所有奇数和正整数 n都变成了 3*n +1 ，但是也表示所有正数都变成了 n/2。没有其他要求说明该数字必须为偶数。
换句话说， (`div` 2)操作仅在 (>0)要求下，没有别的。从技术上讲，这是不正确的，但是如果我们仅获得第一个结果(使用 Maybe Alternative实例基本上可以得到)，它就可以正常工作。如果我们列出所有结果，我们也会得到不正确的结果。
什么时候获得多个结果有趣？也许我们正在为AI编写决策树，我们想通过首先获取所有有效决策，然后随机选择其中一个来人性化行为。或根据情况或其他情况对他们进行排名。