Haskell元组搜索列表

Question

我正在尝试制作一个程序，搜索元组列表(Char, Bool)，如果其中有任何两个冲突元素，则返回true。如果元组中第一个元素(Char(的值相同，但第二个元素不同(Bool(，则两个元组是冲突的。

例如

[('a', True),('a', False)] returns False , 'a'='a' but True != False
[('a', True),('a', True) returns True. , 'a'='a' and True=True
[('a', True),('a', True), ('b', true), ('c', false)] returns true

ListofTupels :: [(a,a)] -> [a]
type ListofTupels = [(Char,Bool)]

该函数的定义类似于

searchValidity :: ListofTupels -> Bool

如何做到这一点？

Answer 1

使用递归。空列表是空洞有效的：

type ListofTuples = [(Char,Bool)]
searchValidity :: ListOfTuples -> Bool
searchValidity [] = True

非空列表由一个有效的尾部和一个不会使列表无效的头部组成。

searchValidity ((c, b):rest) = searchValidity rest && ...

我把填写...作为练习。前奏曲中的lookup函数应该是有用的。

(我把在次二次方时间内完成这项工作作为进一步的练习。在每一步使用lookup会大大降低速度。(