if-statement - 列出 Haskell 中的理解和递归 if 语句

Question

我目前正在通过多种方式练习 Haskell。 使用列表来创建大量有趣的东西。 现在我(认为)在理解 if 语句方面遇到了问题。

我想要做的是制作一个焦点列表，将焦点转移到最左边的项目。 焦点列表已经相当棘手，本质上是两个独立的列表。 它还将整个列表分成两半，并反转后面的列表。

例如。如果你想要创建一个 [0,1,2,3,4,5] 的焦点列表，并且想要焦点在 3 上，则焦点列表将为 [3,4,5][2,1,0]。

我已经制作了三个特定功能。 制作焦点列表数据类型的一种:

data FocusList a = FocusList { 向前::[a], 向后::[a]}

您可以使用它来调用它

fromList :: [a] -> FocusList a
fromList list = FocusList list []

将其从焦点列表更改回列表的方法:

toList :: FocusList a -> [a] 
toList (FocusList fw bw) = reverse bw ++ fw

将其向左移动一次，将 [0,1,2,3,4,5] 更改为 [0,1,2,3, 4,5] 现在看起来像 [2,3,4,5][0,1] 作为焦点列表:

goLeft :: FocusList a -> FocusList a
goLeft (FocusList fw (f:bw)) = FocusList (f:fw) bw

现在，到焦点了。如果我把它一直移到左边。我想使用 goLeft 直到列表的长度为 1。我正在考虑使用递归 if 语句，直到第一个列表的长度等于 1。如果不是，则使用 goLeft。

所以我想到了一个简单的if语句。 (目前)这根本不起作用。 它使用 leftMost::FocusList a -> FocusList a

leftMost (FocusList fw (f:bw)) =  if (length (FocusList fw) == 1)
                                    then FocusList (f:fw) bw
                                    return leftMost
                                   else FocusList fw (f:bw)

我正在以Pythonic的方式思考它。这似乎不起作用。如何使其逻辑递归？

Answer 1

不要使用length，它的成本是O(N)，因为它必须扫描整个列表。如果您改为使用模式匹配，在这种情况下您只需支付 O(1) 成本。

一种简单的方法是使用两个方程，逐个尝试。

leftMost :: FocusList a -> FocusList a
-- if there's only one backward item, leave the list as it is
leftMost (FocusList fw [f]) = FocusList fw [f]
-- otherwise, goLeft, then recurse
leftMost fl                 = leftMost (goLeft fl)

模式[f]仅匹配具有单个项目的列表。它相当于(f:[])。

请注意，如果后面的部分为空，上面的代码将会崩溃。如果这是一个问题，您需要通过添加更多方程来解决这个问题。

或者，可以使用 as 模式来缩短代码:

leftMost :: FocusList a -> FocusList a
leftMost fl@(FocusList fw [f]) = fl    -- fl is the whole input
leftMost fl                    = leftMost (goLeft fl)

如果我们愿意，我们还可以内联goLeft:

leftMost :: FocusList a -> FocusList a
leftMost fl@(FocusList fw [f]) = fl
leftMost (FocusList fw (f:bw)) = leftMost (FocusList (f:fw) bw)

或者甚至处理上面提到的空向后列表问题:

leftMost :: FocusList a -> FocusList a
leftMost fl@(FocusList fw     [f])    = fl
leftMost    (FocusList fw     (f:bw)) = leftMost (FocusList (f:fw) bw)
leftMost    (FocusList (f:fw) [])     = FocusList fw [f]
leftMost    (FocusList []     [])     = error "leftMost: empty list"

最后一种情况涉及空列表，很难以合理的方式处理。您可以选择崩溃并显示错误消息(如上所述)，返回空列表(这是预期的结果吗？)，或者通过返回 Maybe (FocusList a) 向调用者报告错误相反。