哈斯克尔的三角形列表

Question

我必须编写一个函数(不使用预加载的函数(来决定某个整数列表是否为三角形，三角形是指如果它增加到某个数字然后减少，例如：

[2,4,5,7,4,3]，还有：[]，[1]，[1,1]，[1,2,3]，[3,2,1]，[1,2,2]，

[2,2,1](所以不严格增加和减少(

我想出了这个，但我不知道下一步该怎么做，任何建议都值得赞赏：

ex :: [Int] -> Bool
ex [] = True
ex (x:xs) | 

Answer 1

只是为了好玩，我想我会把一个风格截然不同的解决方案放在一起。想象一下，我们没有数字列表，而是在数字减少时带有L的字符串，当它们保持不变时带有E，或者当它们变大时带有G。然后三角形意味着测试该字符串是否在常规语言[LE]*[GE]*中。这就是我们将在此解决方案中执行的操作：编写一个正则表达式并检查数字的摘要是否与之匹配。我正在使用正则表达式应用程序，但如果您愿意，您可以使用自己喜欢的正则表达式库。

{-# LANGUAGE NoMonomorphismRestriction #-}
import Data.Maybe
import Text.Regex.Applicative
triangular = many (sym LT <|> sym EQ) *> many (sym GT <|> sym EQ)
summarize xs = zipWith compare xs (tail xs)
ex = isJust . match triangular . summarize

我们可以在ghci中的所有示例中尝试一下：

*Main> map ex [[2,4,5,7,4,3], [], [1], [1, 2, 3], [3, 2, 1], [1, 2, 2], [2, 2, 1]]
[True,True,True,True,True,True,True]
*Main> ex [2,3,4,3,2,3,4] -- plus one I made up to check it's not const True
False

Answer 2

在开发代码时，我将尝试向您解释一些代码。问题显然可以分为两部分：检测列表的增加部分和列表的减少部分。在Haskell中使用列表的关键思想是，你(如果你手头还没有空列表(总是看列表的头部和尾部，你通常会尝试按这个顺序浏览列表。

因此，让我们编写一个函数来检测列表是否首先非严格递减。当然有几种方法可以做到这一点。让我们尝试一种没有额外参数的递归方法。你已经有一个良好的开端

dec :: [Int] -> Bool
dec [] = True

现在让我们继续模式匹配。下一个不为空的最大列表是包含一个元素的列表，它显然总是在减少：

dec [x] = True

下一步很有趣。如果我们有一个列表，在开头(可能更多(有两个元素(x和y(，那么要使列表减少，显然x >= y需要保留，但剩余的列表，从y开始，需要减少。既然这样就足够了，我们只需要把它写出来

dec (x:y:rest) = x >= y && dec (y:res)

就是这样！

现在到你的锻炼功能，在哪里可以做同样的事情。唯一的区别是，一旦列表无法增加，我们允许检查列表是否可能从此时开始减少：

ex :: [Int] -> Bool
ex [] = True
ex [x] = True
ex (x:y:rest) = (x <= y && ex (y:res)) || dec (x:y:rest)

我希望对我如何编写该代码的解释对您接下来的练习有所帮助。另请注意，还有许多其他更有效的方法可以解决此问题。