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]

Compiler は明らかに Int を [Int] と比較することはできないと言っていますが、言い方がわかりません。

e | e <- entries, e has length i

どんな助けでも大歓迎です！

乾杯

4

2 に答える 2

2

あなたのコードはほとんどOKです：

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]1つずつ取得することを意図しており、それ<-はリスト内包表記でバインドすることによって行われます。

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

さて、[r | r <- xs]と同じな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

アルゴリズム的にも優れています。ただし、存在しない長さの空のランはないため、2つは厳密には同等ではありません。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 に答える
2

groupByから関数を探していますData.List。長さでグループ化する文字列のリストがあります。groupBy関数の型は(a -> a -> Bool) -> [a] -> [[a]]です。2 番目のパラメーターは入力リストで、最初のパラメーターは記述する必要がある関数で、2 つの文字列を取り、それらの長さを比較する必要があります。文字列のリストのリストを返します。各サブリストには同じ長さの文字列が含まれます。

ところで、これを簡潔に書きたい場合は、 のonコンビネータを見てくださいData.Function。

于 2012-11-01T02:48:07.723 に答える