Haskell: List Consrehension/Hash Table Entries

Question

Я пытаюсь поместить кучу слов в хеш-таблицу на основе длины. Слова хранятся в

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 

Любая помощь очень ценится !

Приветствия

Answer 1

Ваш код почти 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] один за другим, и это делается путем <- связывания в списке понимание:

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 

это также лучше алгоритмически. Хотя у него не будет пустых прогонов для несуществующих длин, поэтому они не являются строго эквивалентными. Но это может быть исправлено с другой 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] 

Answer 2

Вы ищете groupBy функции от Data.List. У вас есть список строк, которые вы хотите группировать по их длине. Функция groupBy имеет тип (a -> a -> Bool) -> [a] -> [[a]]. Второй параметр - это ваш список ввода, а первый - это функция, которую вам нужно написать, которая должна взять две строки и сравнить их длины. Он вернет список списков строк, где каждый под-список будет содержать строки одинаковой длины.

Кстати, если вы хотите написать это лаконично, посмотрите на комбинатор on от Data.Function.