16

私はHaskellの初心者です。convertKVList一部のキーが繰り返される可能性のあるキーと値のペアのフラットリストを取得し、それをキーからすべてのキーが一意である値のリストへのマッピングに変換する関数を作成するとします。たとえば、のペアのリストで、Int次の動作が必要です。

> convertKVList [(1, 2), (1, 4), (1, 3), (2, 3)]
[(1,[3,4,2]),(2,[3])]

これは、私がやりたいことを実行するために利用できるライブラリ関数があるはずの十分に一般的なタスクのようですが、私が見たときに何も見つかりませんでした。最後に、誰かが私がで作曲することを提案しMap.toListましたMap.fromListWith (++)、そして私はこれで終わりました：

import Data.Map as Map (toList, fromListWith)

convertKVList :: (Ord a) => [(a, b)] -> [(a, [b])]
convertKVList ls =
  (Map.toList . Map.fromListWith (++) . map (\(x,y) -> (x,[y]))) ls

私の質問は、より経験豊富なHaskellersに関するもので、2つの部分に分かれています。1つは、これをどのように行うか、または「より良い」（読みやすい、より効率的な、またはその両方）方法があるかどうかです。

第二に、どうすれば自分でこれを思い付くことができたでしょうか？タイプを作りたいと思っていたのですが[(a, b)] -> [(a, [b])]、それをHoogleに入れても、何の役にも立ちませんでした。そして、私はData.Mapドキュメントを見ましたが、特に役立つものとして飛び出したことfromListWithもありませんでした。toListだから：あなたはこの問題についてどのように考えますか？（私は、これらの質問の両方が主観的であり、特に2番目の質問であることを認識しています。）

ありがとう！

4

6 に答える 6

9

関数を作成する際の最も重要なポイントの1つは、実行する必要のあることを個別のサブタスク（最終的には関数の合成によってまとめられることが多い）に分割しようとすることです。たとえば、思いついた定義には、次の3つのタスクがあります（適用順に、つまり定義の右から左へ）。

  1. 各ペアの2番目のコンポーネントをシングルトンリストにマップします（これにより、の使用が可能になりますMap.fromListWith）
  2. マップを作成します（同じキーを持つエントリのマージを処理します）
  3. それをリストに変える

私は別の解決策を投稿したかった（それはその間に投稿されたコードMarkの正確なコピーでした;））。ほとんどの場合、同じ目標への異なるルートがあることを明確にするためです。彼の定義では、個別のタスクがあります。

  1. キーでリストを並べ替える
  2. 結果をキーでグループ化する
  3. 希望のタイプのリストに変換します

繰り返しになりますが、関心の分離（モジュール性）は重要な原則です。小さな問題にそれを適用してみてください。経験を積むと、一見難しい問題に対する驚くほど簡単な解決策を思いつくことができます。

于 2013-03-20T03:36:23.430 に答える
8

これは決して標準的ではありませんが：

import Data.List
import Data.Ord
import Data.Function (on)

convertKVList :: Ord a => [(a,b)] -> [(a,[b])]
convertKVList = map (\x -> (fst $ head x,  map snd x)) . groupBy ((==) `on` fst) . sortBy (comparing fst)

Data.Mapをプルしないという利点があります。漸近的に同じである必要があり、ベンチマークされていません。Control.Arrow（（fst .head &&& map snd）のようなもの）を使用して最初のチャンクをクリーンアップできると思いますが、明らかにクリーンではありません。

ただし、それを知っているか、＃haskellで質問する以外に、どのようにしてそれに到達するかはわかりません。

于 2013-03-20T03:25:52.540 に答える
8

Hoogleは型署名でHaskellライブラリを検索できる唯一の検索エンジンではなく、Hackageのごく一部しかカバーしていません。Hayooで型シグネチャを検索すると、[(a,b)]->[(a,[b])]次の2つの実装が見つかりました。

問題に対するあなたの見解に関しては、あなたの関数ではすでにより高いレベルのデータ構造（Map）を持っているので、出力でより原始的な連想リストにダウングレードすることは意味がありません。理由は次のとおりです。

  1. このようなデータを利用できる可能性のあるアルゴリズムのほとんどは、Map入力を取得することでのみメリットがあります。これは、Key-Valueストアを処理するのにはるかに効果的であり、リストが必要な場合は、いつでもそのtoList場で利用できるためです。
  2. MapHaskellでは常に型システムを使用して最大限の証明を行う必要があるため、型レベルで重複キーがないことを意味します。これはそれほど重要ではありません。この原則は、本質的に、「コンパイルすれば機能する」というステートメントを真実に最も近いものにするものです。

言い換えれば、これはあなたの関数の正しい定義です：

convertKVList :: (Ord a) => [(a, b)] -> Map a [b]
convertKVList ls =
  Map.fromListWith (++) . map (\(x,y) -> (x,[y])) $ ls

その型シグネチャのHayooingは、すでに実装されているいくつかの結果ももたらします。

問題へのアプローチに関しては、それは古典的です：「分割統治法！」。クリスは彼の答えにもいくつかの良い点があります。

于 2013-03-20T06:47:05.660 に答える
3

突然変異とSTモナドに浸らなければ、Map.fromListWith解決策（またはを使用するような実質的に同等の代替案HashMap.fromListWith）を改善することはできないと思います。私はそれで行きます。

a基本的に、ミューテーションを使用すると、キーとしてミュータブルハッシュテーブルを使用し、値としてミュータブルリストを使用することで、ほぼ線形時間でこのグループ化を行うことができbます。ただし、ミューテーションがないと、バランスの取れた検索ツリーへの各挿入はO（log n）であるため、さらに悪化します。これは、「挿入」とは、挿入された要素が入るノードにつながる各ツリーノードの新しいコピーを作成することを意味するためです。n回の挿入を行う必要があります。これにより、Map.fromListWith関数のO（n * log n）境界が正確に得られます。もっている。並べ替えもO（n * log n）であるため、事前に関連付けリストを並べ替えても、これは根本的に改善されません。

したがって、O（n * log n）を改善するには、突然変異を伴うデータ構造が必要です。私は簡単なGoogleを実行しましたが、最善の策は、hashtablesライブラリのようなものを使用して標準の命令型アルゴリズムを実装することです（これは試したことがないので、保証できません）。これを使用するには、理解する必要がControl.Monad.STありData.STRefます。モナドは、GHCが純粋関数で「内部的に」突然変異を使用するために提供する手法です。STこれは、問題の関数の外部で副作用が観察されないことを保証するために、いくつかの型システム拡張を使用します。 HaskellWikiにはいくつかの例がありますが、これに慣れるためには、ある程度の学習と練習が必要になる場合があります。

ライブラリをよりよく理解したい、または同様のライブラリをよりよく理解したい場合Data.Mapは、Chris Okasakiの純粋関数型データ構造の本（または本の基になっている彼の論文（PDF））を参照することをお勧めします。HaskellではなくStandardMLに基づいており、データ構造は同じではなく、少し読みにくいかもしれませんが、基本的な本です。

于 2013-03-20T07:43:41.157 に答える
3

これは理解できる解決策のように見え、もう少しクリーンアップできます。

Data.Map（toList、fromListWith）をインポートします
Control.Arrow（秒）をインポートします

convertKVList :: Ord a => [（a、b）]-> [（a、[b]）]
convertKVList=toList。fromListWith（++）。マップ（2番目（：[]））

自分でこれを思い付く方法について：から始めたと仮定するとData.Map、マップを使用して値を等しいキーと組み合わせることができます。Data.Mapon Hackageのドキュメントによるaと、値とkキーのタイプです。

これを知っているとa -> a -> a、aの2つの値を組み合わせMap k aて新しいa値を生成する可能性のある関数を検索して見つけることができます。insertWithこれにより、APIが、、、、などのいくつかの関数に絞り込まれfromListWithますfromAscListWith。

同様に、をに変換するには、Map k aドキュメント[(k, a)]を検索して、、、、、Map k a -> [(k, a)]などのいくつかの関数のみを見つけることができます。あなたの場合、はにインスタンス化されることに注意してください。assocstoListtoAscListtoDescList[(k, a)][(Int, [Int])]

標準のHaskellライブラリを理解するのに役立つと思ったのは、Hackageのソースを表示することです。どの関数が他の関数の観点から実装されているかを確認すると、APIが小さく感じられ、どの関数が基本的な構成要素であるかがわかります。

于 2013-03-20T06:54:53.647 に答える
2

したがって、標準ライブラリにどの関数が含まれているかが実際にはわからないため、私のソリューションではパターンマッチングを使いすぎています。

アイデアは、リストがキーでソートされている場合、移動しながらキー値を収集できるというものでした。最初のKey-Valueリストに追加するか、新しいエントリを作成するかをチェックするロジックを実行するために、パターンとガードを使用して条件を定義しました。そして、リストに値を追加するための短所の自由な使用。

また、元のリストが並べ替えられていない場合は、がありsortByます。

import Data.List
import Data.Ord

ls = [(2, 1), (1, 2), (1, 4), (1, 3), (2, 3)]

addval [] (k, v)= [(k, [v])]
addval ((k1, vals) : xs) (k2, v) | k1 == k2
  = ((k1, (v : vals)) : xs)
addval ls (k, v) = ((k, [v]) : ls)

convert ls = foldl addval [] (sortBy (comparing fst) ls)

醜いコードですが、Mapの使用を避けています。

于 2013-03-20T04:02:08.087 に答える