トラック
/
Factor
Factor
/
演習
/
パーサーの食料庫
パーサーの食料庫

パーサーの食料庫

学習演習

はじめに

Factorのハッシュテーブルは連想配列です。key/valueのペアの集まりで、O(1)で検索できます。より大きなassocsファミリーに属しています。

ハッシュテーブルのリテラル

H{ { "coal" 1 } { "wood" 2 } } .

H{ }は空のハッシュテーブルです。ハッシュテーブルは可変で、キーを追加したり削除したりするにつれて大きくなったり小さくなったりします。元のハッシュテーブルをそのまま残したいときは、先にcloneしてください。ハッシュテーブルを表示するとその中身が表示されますが、順序は挿入した順序とは関係ありません。ハッシュテーブルに順序はないのです。

値の読み取り

at(assocsにあります)は値を読み取ります。キーがなければfを返します。

at      ( key assoc -- value/f )
key?    ( key assoc -- ? )
"coal" H{ { "coal" 1 } { "wood" 2 } } at .   ! => 1
"gold" H{ { "coal" 1 } { "wood" 2 } } at .   ! => f

値の書き込み

set-atは追加または上書きをし、delete-atは削除し、change-atは現在の値に対してquotationを実行します。3つともハッシュテーブルを破壊的に書き換えます。

set-at     ( value key assoc -- )
delete-at  ( key assoc -- )
change-at  ( key assoc quot: ( old -- new ) -- )
H{ } clone 5 "coal" pick set-at .
! => H{ { "coal" 5 } }

inc-at:数を数える近道

inc-at(こちらもassocsにあります)は、あるキーの既存の値に1を足します。キーがなければ1として挿入します。数を数えるのにぴったりです。

inc-at ( key assoc -- )
H{ } clone "coal" over inc-at .
! => H{ { "coal" 1 } }

繰り返しと遅延挿入

assoc-eachはすべての( key value -- )のペアをたどります。cacheはあるキーの値を返し、キーがなければ与えられたquotationで一度だけ計算します。

assoc-each ( assoc quot: ( key value -- ) -- )
cache      ( key assoc quot: ( key -- value ) -- value )

cacheは「探すか、なければ作る」というパターンを1語で表します。一連のキーからハッシュテーブルを組み立てるとき、呼び出しのたびにキーが存在しない場合を扱いたくないときに便利です。

一連のキーにハッシュテーブルの更新を適用する

入力が一連のキーで、キーごとにハッシュテーブルを1回ずつ更新したいときは、eachでその並びを繰り返し、フライドquotation '[ _ … ](fryにあります)を使ってハッシュテーブルをループ本体に埋め込みます。たとえば、キーのリストを削除するには次のようにします。

{ "wood" "iron" } H{ { "coal" 5 } { "wood" 3 } { "iron" 2 } } clone
[ '[ _ delete-at ] each ] keep .
! => H{ { "coal" 5 } }

'[ _ delete-at ]はスタック上でそのすぐ下にあるハッシュテーブルを取り込みます。こうすることで、繰り返しのたびにeachがキーを渡すだけでよくなります。keepは、最後の.のためにハッシュテーブルを保持したままquotationを実行します。

並びからハッシュテーブルを組み立てる

map>assoc(assocsにあります)は、並びに対してquotationをマップし、( elt -- key value )の結果を、見本の型のassocに集めます。

map>assoc ( seq quot: ( elt -- key value ) exemplar -- assoc )
{ "wood" } [ dup length ] H{ } map>assoc .
! => H{ { "wood" 4 } }

キー、値、ペア

keysとvalues(assocsにあります)はキーだけ、または値だけを返します。>alistは{ key value }のペアを返します。

keys   ( assoc -- keys )
values ( assoc -- values )
>alist ( assoc -- alist )
H{ { "wood" 11 } { "coal" 7 } } keys .     ! the keys (order not guaranteed)
H{ { "wood" 11 } { "coal" 7 } } values .   ! the matching values

keysとvaluesは対応しています。ある位置の値は、同じ位置のキーに対応する値です。

sort-keys(sortingにあります)は{ key value }のペアをキーで並べ替えて返します。

H{ { "wood" 11 } { "coal" 7 } } sort-keys .
! => { { "coal" 7 } { "wood" 11 } }

ペアからハッシュテーブルに戻す

>hashtable(hashtablesにあります)は>alistの逆です。任意のassocを、O(1)で検索できるハッシュテーブルに変換します。多くの場合、{ key value }のペアからなるalistを変換するのに使います。

>hashtable ( assoc -- hashtable )
{ { "coal" 7 } { "wood" 11 } } >hashtable .
! => H{ { "wood" 11 } { "coal" 7 } }   (entry order not guaranteed)

ペアのリストを組み立てたり変換したりしたあと、それをハッシュテーブルに戻してキーで項目を引きたくなったときに便利です。

説明

船のパーサーとして、食料庫の在庫表を管理しています。在庫表はハッシュテーブルで、それぞれのキーが品物の名前、値が在庫数です。

1. 配列から在庫表を組み立てる

create-inventoryを定義してください。品物名の配列を受け取り、重複しないそれぞれの名前とその個数を対応させたハッシュテーブルを返します。

{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }

2. 品物を追加する

add-itemsを定義してください。在庫表と品物の配列を受け取り、挙げられた品物ごとに個数を増やした新しい在庫表を返します。元の在庫表は変更しないでください。

H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }

3. 個数を減らす

decrement-itemsを定義してください。在庫表と品物の配列を受け取り、挙げられた品物ごとに個数を1つ減らした新しい在庫表を返します。個数が0を下回ることはなく、もともと在庫表にない品物は除きます(マイナスの項目は追加されません)。

H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }

4. 品物を完全に取り除く

remove-itemを定義してください。在庫表と1つの品物を受け取り、その品物を取り除いた新しい在庫表を返します。その品物がなければ、変更していないコピーを返します。

H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }

5. 利用できる品物を一覧にする

list-inventoryを定義してください。在庫表を受け取り、在庫数が0より大きい品物だけを含み、名前のアルファベット順に並べた{ name quantity }の組の配列を返します。

H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
GitHubで編集する リンクは新しいウィンドウまたはタブで開きます
Factor Exercism

パーサーの食料庫を始める準備はできましたか?

Exercismに登録すれば、47個のコンセプト163個の演習、そして本物の人間によるメンタリングとともに、Factorを学んでマスターできます。すべて無料です。