关于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 

不幸的是它包含(否则为dx)三次.

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

我知道我们可以将条件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.如果没有,则继续进行下一个分支c3,依此类推,直到它到达某个动作(或已遍历整个树).

但首先你会需要一个数据类型来告诉的要求(的区别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非常强大,可以像这样定义自定义的"语言内部语言".

然后,您需要在树中搜索您可以达到的第一个操作.

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 Maybe(asum)来阻止第一次成功击中.这反过来意味着它不会徒劳地计算任何分支的条件(如果计算是昂贵的,这是有效且重要的)并且它应该处理无限的决策树.

你可以decide更充分地利用这个Alternative课程,但是我选择专攻它,Maybe以便不写一本关于这个的书.使它更加通用可能会让你有一个奇特的monadic决定,这将是非常酷!

但是,最后,作为一个非常简单的例子 - 采取Collat​​z猜想.如果你给我一个号码,并问我下一个号码应该是什么,我可以建立一个决策树来找出答案.树可能如下所示:

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

所以数字必须大于0,然后如果它是奇数你乘以3并加一,否则你将它减半.测试运行表明

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

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

编辑就像一年后:对于Alternative的概括实际上非常简单,而且相当有趣.该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来组装输入满足的"所有"动作.这揭示了我们collatz树中的"错误" - 如果我们仔细观察它,我们会看到所有奇数和正整数n转向3*n +1 但它也表示所有正数转向n/2.没有额外要求说数字必须是均匀的.

换句话说,该(`div` 2)行动仅在(>0)要求之下,而不是其他任何内容.这在技术上是不正确的,但是如果我们得到第一个结果(这基本上是使用MaybeAlternative实例的那个),它就会起作用.如果我们列出所有结果,我们也会得到一个不正确的结果.

何时获得多个结果有趣？也许我们正在为AI编写决策树,我们希望通过首先获得所有有效决策,然后随机选择其中一个来使行为人性化.或者根据他们在环境中的优势或其他方面对他们进行排名.

Answer 2

你可以使用警卫和一个where条款:

f x | cb && c2 x = a x
    | cb && c3 x && c4 x = b x
    | otherwise = d x
  where cb = c1 x

Answer 3

如果您只是担心将它们写出来,那么这就是where块的用途

f x = 
  case () of
    () | c1 && c2       -> a x
       | c1 && c3 && c4 -> b x
       | otherwise      -> d x
  where
    c1 = ...
    c2 = ...
    c3 = ...
    c4 = ...

并不是说我正在使用这个case技巧为守卫声明引入一个新的地方.我不能在函数定义本身使用保护,因为该where子句不会覆盖所有守卫.你可以使用if相同的,但是守卫有很好的传递语义.

Answer 4

您可以使用另一种模式:我不会在您的具体示例中使用它,但是我使用它的情况非常类似.

f x = case (c1 x, c2 x, c3 x, c4 x) of
  (True,True,_,_) -> a x
  (True,False,True,True) -> b x
  _ -> d x

实际上只评估选择采用哪条路径所需的最低评估:c2 x除非c1 x是,否则实际上不会评估True.