我必须编写一个函数(不使用预加载函数)来决定某个 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) |
我必须编写一个函数(不使用预加载函数)来决定某个 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) |
只是为了好玩,我想我会拼凑出一个风格迥异的解决方案。想象一下,我们有一个字符串,而不是一个数字列表,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
我会在开发时尝试向您解释一些代码。问题显然可以分为两部分:检测列表的增加部分和列表的减少部分。在 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)
我希望对我如何编写该代码的解释可以帮助您进行下一个练习。另请注意,还有许多其他更有效的方法可以解决此问题。