2

我必须编写一个函数（不使用预加载函数）来决定某个 Ints 列表是否是三角形的，三角形的意思是它是否增加到一定数量然后减少，例如：

[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) |
4

2 回答 2

4

只是为了好玩，我想我会拼凑出一个风格迥异的解决方案。想象一下，我们有一个字符串，而不是一个数字列表，L当数字减少时，E当它们保持不变时，或者G当它们变大时。然后是三角形意味着测试该字符串是否是常规语言[LE]*[GE]*。所以这就是我们在这个解决方案中要做的：编写一个正则表达式并检查数字的摘要是否匹配它。我正在使用regex-applicative，但如果你愿意，你可以使用你最喜欢的 regex 库。

{-# 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
于 2013-10-06T23:26:16.417 回答
3

我会在开发时尝试向您解释一些代码。问题显然可以分为两部分：检测列表的增加部分和列表的减少部分。在 Haskell 中使用列表的关键思想是您（如果您手头没有空列表）总是查看列表的头部和尾部，并且您通常会尝试在其中浏览列表命令。

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

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

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

dec [x] = True

下一步很有趣。如果我们有一个在开头（可能更多）有两个元素 (x和) 的列表，那么对于要递减的列表，显然需要保持，但从 开始的剩余列表也需要递减。就足够了，我们只需要写出来yx >= yy

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)

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

于 2013-10-06T20:51:29.773 回答