スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#雑記 リストの内容比較

fumokmmさんの記事BlUEPIXYさんの記事をみてやってみました。 
 
お題は次の通りです。 

----------------------------------------------------------------------------------------------
二つのリスト(左・右)の内容を比較し、片方にしかないものと両方に在るものを出力するプログラムを書いて下さい。
 
条件
・リストの入力方法、出力方法は自由とします。
・入力されるリストの内容は未ソートかつ重複がある可能性を考慮して下さい。
・出力されるリストは、左のリストにのみある内容、右のリストにのみある内容、両方のリストにある内容の三種類とします。
・出力されるリストは辞書順ソートかつ重複は除去した形式として下さい。
 
サンプル入力リスト:
[listL] aaa bbb ccc bbb eee hhhh
[listR] bbb ddd eee fff ggg iiiii
 
サンプル出力リスト:
[left only] aaa ccc hhhh
[right only] ddd fff ggg iiiii
[both] bbb eee
 
また、余裕のある方は以下のように左右の内容を並べて出力して下さい。
 
サンプル出力リスト(余裕のある方用):
aaa  |
bbb  | bbb
ccc  |
     | ddd
     | eee
     | fff
     | ggg
hhhh |
     | iiiii
 
----------------------------------------------------------------------------------------------
 
F#でやるとするとSetを使うのが王道だと思うのですが、これはBlUEPIXYさんがやられてますので、ここはlistでやってみたいと思います。
 
まずリストを与えると降順にならべ重複を取り除く関数sortDesAndRemoveDupを定義します。
 
> let sortDesAndRemoveDup in_lst =
    let sortedLst = List.sort in_lst
    List.fold (fun s ele -> if ele = Seq.head s then s else ele :: s) [List.head sortedLst] (List.tail sortedLst);;
 
val sortDesAndRemoveDup : 'a list -> 'a list when 'a : comparison
 
実行例
 
> sortDesAndRemoveDup [1;3;8;4;3];;
val it : int list = [8; 4; 3; 1]
 
> sortDesAndRemoveDup ["ccc";"bbb";"aaa";"bbb";"eee";"hhhh"];;
val it : string list = ["hhhh"; "eee"; "ccc"; "bbb"; "aaa"]
 
次に降順にならべられ重複を取り除いた二つのリストから、「左のリストにのみある内容」、「右のリストにのみある内容」、「両方のリストにある内容」、「二つを統合した内容」のタプルを返す関数を定義します。
 
> let rec siwakeSub lLst rLst (lOnly,rOnly,both,res) =
   match lLst,rLst with
   | [],[]          ->  (lOnly,rOnly,both,res)
   | lHd::lRem,[]   ->  siwakeSub lRem [] (lHd::lOnly, rOnly, both,(Some(lHd),None)::res)
   | [],rHd::rRem   ->  siwakeSub [] rRem (lOnly,rHd::rOnly, both, (None,Some(rHd))::res)
   | lHd::lRem,rHd::rRem 
          when lHd > rHd -> siwakeSub lRem rLst (lHd::lOnly,rOnly, both, (Some(lHd),None)::res)     
   | lHd::lRem,rHd::rRem 
          when lHd < rHd -> siwakeSub lLst rRem (lOnly,rHd::rOnly, both, (None,Some(rHd))::res)     
   | lHd::lRem,rHd::rRem 
          when lHd = rHd -> siwakeSub lRem rRem (lOnly,rOnly,lHd :: both, (Some(lHd),Some(rHd))::res)     
   | _                   -> failwith "error" ;;
 
val siwakeSub :
  'a list ->
    'a list ->
      'a list * 'a list * 'a list * ('a option * 'a option) list ->
        'a list * 'a list * 'a list * ('a option * 'a option) list
    when 'a : comparison
 
使ってみます。
 
> siwakeSub (sortDesAndRemoveDup ["ccc";"bbb";"aaa";"bbb";"eee";"hhhh"])
          (sortDesAndRemoveDup ["bbb";"ddd";"eee";"fff";"ggg";"iiii"]) 
          ([],[],[],[]);;
val it :
  string list * string list * string list *
  (string option * string option) list =
  (["aaa"; "ccc"; "hhhh"], ["ddd"; "fff"; "ggg"; "iiii"], ["bbb"; "eee"],
   [(Some "aaa", null); (Some "bbb", Some "bbb"); (Some "ccc", null);
    (null, Some "ddd"); (Some "eee", Some "eee"); (null, Some "fff");
    (null, Some "ggg"); (Some "hhhh", null); (null, Some "iiii")])
    
 
以上をふまえてまとめます。
 
let sortDesAndRemoveDup in_lst =
    let sortedLst = List.sort in_lst
    List.fold (fun s ele -> if ele = Seq.head s then s else ele :: s) [List.head sortedLst] (List.tail sortedLst)
 
 
let siwake in_lLst in_rLst =
    let rec siwakeSub lLst rLst (lOnly,rOnly,both,res) =
       match lLst,rLst with
       | [],[]          ->  (lOnly,rOnly,both,res)
       | lHd::lRem,[]   ->  siwakeSub lRem [] (lHd::lOnly, rOnly, both,(Some(lHd),None)::res)
       | [],rHd::rRem   ->  siwakeSub [] rRem (lOnly,rHd::rOnly, both, (None,Some(rHd))::res)
       | lHd::lRem,rHd::rRem 
              when lHd > rHd -> siwakeSub lRem rLst (lHd::lOnly,rOnly, both, (Some(lHd),None)::res)     
       | lHd::lRem,rHd::rRem 
              when lHd < rHd -> siwakeSub lLst rRem (lOnly,rHd::rOnly, both, (None,Some(rHd))::res)     
       | lHd::lRem,rHd::rRem 
              when lHd = rHd -> siwakeSub lRem rRem (lOnly,rOnly,lHd :: both, (Some(lHd),Some(rHd))::res)     
       | _                   -> failwith "error" 
    siwakeSub (sortDesAndRemoveDup in_lLst) (sortDesAndRemoveDup in_rLst) ([],[],[],[])
 
let disp1 msg lst =
    printf "%s " msg
    lst |> List.iter (fun s -> printf "%A " s) 
 
let disp2 lst =
    lst |> List.iter (fun s ->
                        match s with
                        |Some(x),None    -> printfn "%A |" x
                        |None,Some(y)    -> printfn " | %A" y
                        |Some(x),Some(y) -> printfn "%A |%A" x y
                        |_               -> failwith "error")
 
let dispAll (left,right,both,res) =
    disp1 "[left  only]" left
    printfn ""
    disp1 "[right only]" right
    printfn ""
    disp1 "[both      ]" both
    printfn ""
    disp2 res
 
(実行例)「余裕がある人用」はきれいにそろってません。
 
> dispAll (siwake ["aaa";"bbb";"ccc";"bbb";"eee";"hhhh"] ["bbb";"ddd";"eee";"fff";"ggg";"iiii"]);;
[left  only] "aaa" "ccc" "hhhh" 
[right only] "ddd" "fff" "ggg" "iiii" 
[both      ] "bbb" "eee" 
"aaa" |
"bbb" |"bbb"
"ccc" |
 | "ddd"
"eee" |"eee"
 | "fff"
 | "ggg"
"hhhh" |
 | "iiii"
val it : unit = ()
 
> dispAll (siwake [3;1;7;9;11;2] [6;9;8;4;6;3]);;
[left  only] 1 2 7 11 
[right only] 4 6 8 
[both      ] 3 9 
1 |
2 |
3 |3
 | 4
 | 6
7 |
 | 8
9 |9
11 |
val it : unit = ()
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

気付いているとは思いますが・

元々の所(つまりここで引用されている部分)の
>サンプル出力リスト(余裕のある方用):
には、間違いがあります。

ありゃ本当だ

いやいや全然気がついていませんでした。
BLUEPIXYさんの注意力をみならいたいものです。
プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。