我正在尝试解决一个有关字母表的Haskell练习。 给定按新字母顺序排列的单词列表，请找到这个新字母表。
例如，给定单词 ["ab","abd","abc","ba","bd","cc"]，
可能的新字母表是"abdc"或"adbc"。
我开始计算所有可能的字母表顺序。
alfabet :: Eq a => [[a]] -> [[a]]
alfabet list = permutations $ nub $ concat $ list
filter 函数，也尝试编写自己的排序函数，使得当我按照新顺序对单词进行排序时，结果列表与输入列表相同，因此字母是正确的。但都没有成功。有多种方法可以处理这个问题。你建议的方法是生成所有可能的字母表，然后通过筛选与示例数据一致的那些来过滤它们。我将先向您展示一种实现方式。
另一种方法是将示例数据中的信息提炼出来，形成关于字母顺序的某些信息（数学家称之为部分排序），然后将其扩展到所有可能的排序。
import Data.List (permutations, nub, sort)
我将使用类型同义词Alphabet来明确哪些列表是可能的字母表，哪些是单词，并基于字母表（byAlphabet）定义一个排序，然后通过lexiographic排序将其扩展到应用于列表。
type Alphabet a = [a]
byAlphabet :: Eq a => Alphabet a -> a -> a -> Ordering
byAlphabet alphabet x y
| x == y = EQ
| otherwise = if y `elem` (dropWhile (/=x) alphabet) then LT else GT
lexiographic :: (a->a->Ordering) -> [a]->[a]->Ordering
lexiographic cmp [] [] = EQ
lexiographic cmp [] _ = LT
lexiographic cmp _ [] = GT
lexiographic cmp (x:xs) (y:ys) = case cmp x y of
EQ -> lexiographic cmp xs ys
x -> x
我们需要检查给定的单词列表是否与给定的数据 consistentWith 相符：
consistentWith :: Eq a => [[a]] -> Alphabet a -> Bool
consistentWith xss alphabet = all (/=GT) $
zipWith (lexiographic $ byAlphabet alphabet) xss (tail xss)
你似乎在使用可能的字母列表时遇到了困难，但你知道你可以使用 filter：
anyOKby :: Eq a => [[a]] -> [Alphabet a] -> [Alphabet a]
anyOKby sortedWords = filter (consistentWith sortedWords)
提供一个稍作编辑的alfabet函数，该函数过滤掉不起作用的部分。
alfabet :: Eq a => [[a]] -> [Alphabet a]
alfabet list = anyOKby list $ permutations $ nub $ concat $ list
example = ["ab","abd","abc","ba","bd","cc"]
这个按预期工作：
ghci> byAlphabet "abc" 'c' 'a'
GT
ghci> lexiographic (byAlphabet "abc") "ccba" "ccbc"
LT
ghci> consistentWith example "abcd"
False
ghci> consistentWith example "abdc"
True
ghci> alfabet example
["abdc","adbc"]
现在这种方法相对较慢，因为它生成许多潜在的字母表然后缓慢地过滤它们。第一次尝试时，我放弃了等待alfabet (sort $ words "hello there the their he and at ah eh")的打印输出。
我将使用一种数据类型来显示哪些字符在其他字符之前，因此'a' :<: 'b'表示'a'必须在字母表中排在'b'之前。
data CMP a = a :<: a deriving (Eq,Show)
为了简单一些，我将使用[CMP a]而非Maybe (CMP a)来代替，因为使用concat比引入Data.Maybe (catMaybes)更加容易。但每个相邻的词对于字母表最多只能提供一个比较事实。facts函数使用了巧妙的zipWith f xs (tail xs)技巧，用f从列表中的每个相邻的一对中生成一个结果。
justTheFirst :: [a] -> [a]
justTheFirst [] = []
justTheFirst (a:_) = [a]
fact :: Eq a => [a] -> [a] -> [CMP a]
fact xs ys = justTheFirst . filter neq $ zipWith (:<:) xs ys where
neq (a:<:b) = a /= b
facts :: Eq a => [[a]] -> [CMP a]
facts xss = nub . concat $ zipWith fact xss (tail xss)
例子：
ghci> fact "wellbeing" "wellington"
['b' :<: 'i']
*Main ghci> facts example
['d' :<: 'c','a' :<: 'b','a' :<: 'd','b' :<: 'c']
我们将使用一种数据类型来表示偏序——一个字符列表和一组比较，我们将使用facts函数从样本排序的单词中生成比较，并使用您的nub.concat技巧获取字母本身：
data Partial a = Partial {chars :: [a], order :: [CMP a]} deriving Show
partial :: Eq a => [[a]] -> Partial a
partial xss = Partial {chars = nub $ concat xss, order = facts xss}
例子：
ghci> partial example
Partial{chars = "abdc",order = ['d' :<: 'c','a' :<: 'b','a' :<: 'd','b' :<: 'c']}
要从偏序中生成可能的字母表，我们首先需要找到哪些元素可以放在最前面。只要你不比任何东西大，就可以放在最前面，因此让我们列出 非大元素 的列表。如果我们将潜在的第一个字母放在字母表的最前面，我们可以从剩余的偏序中 移除 它：
nonBigs :: Eq a => [CMP a] -> [a] -> [a]
nonBigs lts as = filter (not.big) as where
big a = a `elem` (map (\ (_ :<: a) -> a) lts)
remove :: Eq a => a -> [CMP a] -> [CMP a]
remove a = filter no_a where
no_a (x :<: y) = not $ a `elem` [x,y]
示例: （例子中唯一不比某个东西大的是'a'，并且有两个事实不涉及到 'a'）
ghci> facts example
['d' :<: 'c','a' :<: 'b','a' :<: 'd','b' :<: 'c']
ghci> nonBigs (facts example) "abcd"
"a"
ghci> remove 'a' (facts example)
['d' :<: 'c','b' :<: 'c']
让我们将非Bigs与已删除该字母的偏序配对，以获取所有可能的最小元素以及如何继续：
minima :: Eq a => Partial a -> [(a,Partial a)]
minima (Partial as lts) =
[(a,Partial (filter (/=a) as) (remove a lts) )|a <- nonBigs lts as]
例子：在这个例子中，你必须先有 'a'，但是之后你可以选择放置 'b' 或者 'd'：
ghci> minima $ partial example
[('a',Partial {chars = "bdc", order = ['d' :<: 'c','b' :<: 'c']})]
ghci> minima $ Partial {chars = "bdc", order = ['d' :<: 'c','b' :<: 'c']}
[('b',Partial {chars = "dc", order = ['d' :<: 'c']}),
('d',Partial {chars = "bc", order = ['b' :<: 'c']})]
复杂的部分是使用偏序关系提供的"有向图"来生成所有可能的树形路径。我们将使用一个树生长函数f :: input -> [(output,input)]，它可以告诉您继续进行的所有可能方式。如果没有给出任何答案，我们需要[[]]，一个空路径，我们将通过在每个可能性(treePaths f i')的前面放置可能的第一个元素(map (o:))来递归地生长它：
treePaths :: (input -> [(output,input)]) -> input -> [[output]]
treePaths f i = case f i of
[] -> [[]]
pairs -> concat [map (o:) (treePaths f i') | (o,i') <- pairs]
alphabets list = treePaths minima (partial list)
alphabets的长度几乎是瞬间完成的，但计算alfabet的长度在我（相当旧的）笔记本电脑上需要超过2分钟；只生成您想要的输出比生成每个输出并将其丢弃更快。ghci> alphabets example
["abdc","adbc"]
ghci> length $ alphabets (sort $ words "hello there the their he and at ah eh")
15120
ghci> length $ alfabet (sort $ words "hello there the their he and at ah eh")
15120
["ab","abd","abc","ba","bd","cc"]使用\ls -> map head $ group $ map head ls，那么会得到"abc"。如果您对第二个符号重复类似的过程，其中第一个符号相同，则还会有"b"、"ad"和"c"。这些部分字母表足以推断出所有可能的完整字母表。('a', 'b')在列表中，那么'a'就在'b'之前。然后使用该集合作为比较器，逐一将符号插入到所有可能的位置。确保考虑到不确定的排序。