내장이 있나요?

Question

I 형

[[(a, b)]] -> [(a, [b])]

및 Hoogle tells me there isn't one의 함수를 찾고 있어요, 그래서 쓴이 : 중요한 순서대로

transpose :: (Eq a) => [[(a, b)]] -> [(a, [b])] 
transpose alists = uncurry zip $ foldl combine ([], []) alists 
    where combine memo new = foldl tally memo new 
      tally ([], []) (k, v) = ([k], [[v]]) 
      tally ((ksHead:ksRest), (vsHead:vsRest)) (k, v) = 
       if k == ksHead 
       then (ksHead:ksRest, (v:vsHead):vsRest) 
       else (ksHead:ks, vsHead:vs) 
        where (ks, vs) = tally (ksRest, vsRest) (k, v) 

:

1. 이 있습니까 실제로 Hoogle이 알지 못하는이 내장형?
2. transpose은이 이름이 맞습니까?
3. 더 좋은 (더 읽기 쉽고 더 뛰어난) 방법이 있습니까?

사람이 맛에 관심 때문에 편집 :

I 앱 순위 스택을 쓰고 있어요, 그리고 사용자의 투표 용지가 [(Candidate, Rank)]의 형태로 와서. 예를 들어 Borda count으로 우승자를 계산하려면 해당 투표를 결합하여 각 Candidate의 순위를 집계해야합니다. 보다 일반적인 문제에 대한 의견도 환영합니다.

Answer 1

transpose은 대개 행렬 전치 행을 따라 목록 연산을 의미하는 데 사용됩니다. 실제로, Data.List.transpose 정확히 않습니다.

무엇이 코드가 제대로 작동하는지 알 수 없습니다. 솔직히 정말 복잡합니다. 이런 뜻인가요?

import Data.List 
import Data.Function 
import Control.Arrow 

groupByKey :: Ord a => [[(a, b)]] -> [(a, [b])] 
groupByKey = map (fst . head &&& map snd) . groupBy kEq . sortBy kCmp . concat 
    where 
    kEq = (==) `on` fst 
    kCmp = compare `on` fst 

이 당신이 Ord a에 제약 조건을 업그레이드하고있는 것입니다 O의 알고리즘을 개선하는 경우 (N 로그 n) 대신 O의 (n은^2).

Answer 2

당신은 훨씬 쉽게 이것에 대한 맵 데이터 구조를 사용하는 것이 좋습니다 :

import Data.Map (Map) 
import qualified Data.Map as Map 

transpose: Ord a => [(k, v)] -> Map k [v] 
transpose = Map.fromListWith (++) [] . map (\(k, v) -> (k, [v]) 

는 사실이 기본적으로 문서 fromListWith 위해주는 예입니다.

Answer 3

당신은 당신의 이름 선택에 의해 암시 의미가 산만하지, 하나의 문자 변수를 사용하여 코드에서 숨겨진 구조를 밝히기 위해서 자신을 도움이 될 것이다 :이 작업을 조금 부 자연스러운

g :: (Eq a) => [[(a, b)]] -> [(a, [b])] 
g alists = uncurry zip $ foldl (foldl f) ([], []) alists 
    where 
      f ([], []) (k, v) = ([k], [[v]]) 
      f ((h:t), (u:s)) (k, v) 
      | k == h = (h:t, (v:u):s) 
      | otherwise = (h:q, u :r) where (q, r) = f (t, s) (k, v) 
         -- ((h:) *** (u:)) $ f (t,s) (k,v) 

중간 데이터를 unzip에 넣고 출력을 위해 다시 핑합니다. zip.그에 대한 필요, 우리는 출력으로 임시 데이터의 동일한 유형의 작업을 할 수 없습니다 : f가하는 paramorphism를 "삽입"의 일종이라고 지금은 분명하다

g2 :: (Eq a) => [[(a, b)]] -> [(a, [b])] 
g2 alists = foldl (foldl f) [] alists 
    where 
      f [] (k, v) = [(k,[v])] 
      f ((a,b):t) (k, v) 
      | k == a = (a,v:b):t 
      | otherwise = (a,b):f t (k,v) 

을

  f xs (k, v) = para (\(a,b) t r -> if a==k then (a,v:b):t 
                else (a, b):r) 
          [(k,[v])] xs 
para c z [] = z 
para c z (x:t) = c x t $ para c z t 

foldl (foldl f) [] alists === foldl f [] $ concat alists 그것은 (Ord a) 제약으로 전환 할 수있는 경우와, 그 효율은 향상 f 재 구현 될 수

g3 :: (Ord a) => [[(a, b)]] -> [(a, [b])] 
g3 = foldl f [] . concat 
    where 
    f xs (k, v) = para (\(a,b) t r -> if k < a then (k,[v]):(a,b):t 
            else if a==k then (a,v:b):t 
            else    (a, b):r) 
         [(k,[v])] xs 

는

g4 :: (Ord a) => [[(a, b)]] -> [(a, [b])] 
g4 alists = foldt u [] 
       . map (map (\(a,b) -> (a,[b])) . sortBy (comparing fst)) 
       $ alists 
    where 
    u xs [] = xs 
    u [] ys = ys 
    u xs@((a,b):t) ys@((c,d):r) = case compare a c of 
     LT -> (a,b) : u t ys 
     EQ -> (a,b++d) : u t r 
     GT -> (c,d) : u xs r 

foldt f z [] = z 
foldt f z [x] = x 
foldt f z xs = foldt f z $ pairwise f xs -- tree-like folding 
pairwise f (a:b:t) = f a b : pairwise f t 
pairwise f xs  = xs 

comparing

는 Data.Ord에서, 우리는 the other route합니다 ( concat보다) 이동 및 병합의 트리를 통해 입력 목록에 가입 할 수 있습니다, 더이 코드의 복잡성을 향상시킬 수 있습니다. 데이터 조각이 이미 정렬 된 경우 (시나리오에서 가능성이 있음) 추가 알고리즘 이득을 위해 sortBy 부분을 생략 할 수 있습니다. 따라서이 버전은 일종의 mergesort입니다 (정렬없이 병합 만 가능).