如何在haskell中同时使用2个列表

Question

我正在尝试解决有关字母表的haskell练习.给定一个新的字母顺序的单词列表,找到这个新的字母表.

例如,给定单词["ab","abd","abc","ba","bd","cc"],新的可能字母表是"abdc"或"adbc".

我开始计算所有可能的字母顺序

alfabet :: Eq a => [[a]] -> [[a]]
alfabet list = permutations $ nub $ concat $ list

在此之后,我想我应该过滤掉那些错误的字母表,但我似乎无法传递足够的信息.我已经尝试使用内置filter函数,我尝试编写自己的排序函数,这样当我按新顺序对单词进行排序时,结果列表与输入列表相同,因此字母表是正确的.一切都无济于事.

我想我遇到的最大问题是我需要能够同时处理两个列表(单词和不同的字母表)并以不同的方式循环它们.

任何提示或帮助？谢谢

Answer 1

解决这个问题的方法不止一种。您建议的方法是根据您拥有的字母生成所有可能的字母表，然后根据与示例数据一致的字母过滤掉它们。我将首先向您展示一种方法。

另一种方法是将示例数据中的信息提取为有关字母可以按什么顺序排列的一些信息（数学家称之为部分排序），然后将其扩展到所有可能的排序。

方法一：过滤所有可能的字母表

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")打印。

方法 2：找到偏序并扩展它

我将使用一种数据类型来显示哪些字符在其他字符之前，因此'a' :<: 'b'表示在字母表中'a'必须在之前'b'

data CMP a = a :<: a deriving (Eq,Show)

示例数据的比较事实

我将使用[CMP a]而不只是Maybe (CMP a)因为它比concatto更容易import Data.Maybe (catMaybes)，但是每一对相邻的单词最多可以给出一个fact关于字母表的比较。这些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。如果我们将潜在的第一个字母放在字母表的前面，我们可以remove从剩余的部分顺序中得到它：

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']

让我们将 nonBigs 与删除该字母的部分排序配对，以获得所有可能的最小元素以及如何从那里继续：

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)]来告诉您所有可能的继续方式。如果这没有给你任何我们需要的答案[[]]，一个空路径，我们将通过将可能的第一个元素放在map (o:)每个可能性（treePaths f i'）的前面（）来递归地增长：

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