1

我正在尝试根据长度将一堆单词放入哈希表中。单词存储在

data Entry = Entry {word :: String, length :: Int} deriving Show

现在，我已经将所有单词存储在“条目”中，这是一个条目列表。然后，我的哈希表定义如下：

type Hash = [Run]
type Run = [Entry]

现在我试图弄清楚如何将条目放入哈希表中。以下是我目前的尝试

maxL = maximum [length e | e <- entries]
runs = [r | r <- [e | e <- entries, length e == i]] where i = [1..maxL]

编译器明显告诉我 Int 不能和 [Int] 比较，但我不知道怎么说

e | e <- entries, e has length i

任何帮助深表感谢！

干杯

4

2 回答 2

2

您正在寻找groupBy来自 的功能Data.List。你有一个字符串列表，你想按它们的长度对其进行分组。该groupBy函数具有类型(a -> a -> Bool) -> [a] -> [[a]]。第二个参数是你的输入列表，第一个是你需要编写的函数，它应该接受两个字符串并比较它们的长度。它将返回一个字符串列表列表，其中每个子列表将包含相等长度的字符串。

顺便说一句，如果您想简洁地编写此代码，请查看on.Data.Function

于 2012-11-01T02:48:07.723 回答
2

您的代码几乎可以：

maxL = maximum [length e | e <- entries]
runs = [r | r <- [e | e <- entries, length e == i]] where i = [1..maxL]

除非那样where做。它不是 ; 的同义词foreach。但对于let：

runs = let i = [1..maxL] 
       in [r | r <- [e | e <- entries, length e == i]]

所以，length e是一个整数，但是i是一个整数[1..maxL]列表。您打算一一i接受这些值，这是通过在列表理解中绑定来完成的：[1..maxL]<-

runs = [ [r | r <- [e | e <- entries, length e == i]] | i <- [1..maxL]]

现在，[r | r <- xs]与 just 相同xs，因此变为

runs = [ [e | e <- entries, length e == i] | i <- [1..maxL]]

使用“标准”功能，这被写成

import Data.List (sortBy)
import Data.Ord  (comparing)

runs = group $ sortBy (comparing length) entries

它在算法上也更好。虽然，对于不存在的长度，它不会有空运行，所以两者并不是严格等价的。但这可以通过另一个O(n)结果来解决，

-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])

runs' = snd $ mapAccumL 
               (\a@ ~((k,g):t) i-> if null a || i<k then (a,[]) else (t,g))
               [ (length $ head g, g) | g<- runs]
               [ 1..maxL]
于 2012-11-01T09:27:17.603 回答