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 回答