スポンサーサイト

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

F#入門基本編落穂拾い その19 (再帰的型定義、リスト構造(1))

まずは次の定義をみてください。
 
> type myList =
    |Empty
    |Ele of (int * myList)  ;; //()は不要
    
discriminated unionはEmptyもしくは、Val of int * myListというタプルの値を持つという定義です。
今myListという型の定義をしていたのですが、その定義の中で、再帰的にmyListが使われています。
それでは、どういうものがこの型の型かいくつか例を挙げてみます。
 
> let t0 = Empty;; //EmptyはもちろんmyList型
val t0 : myList = Empty
 
> let t1 =  Ele(1,t0);;  //t0もmyList型
val t1 : myList = Ele (1, Empty)
 
> let t2 =  Ele(2,t1);;//t1もmyList型
val t2 : myList = Ele (2, Ele (1, Empty))
 
> let t3 =  Ele(5,t2);;//t2もmyList型
val t3 : myList = Ele (5, Ele (2, Ele (1, Empty)))
 
> let t4 =  Ele(7,t3);;//t3もmyList型
val t4 : myList = Ele (7, Ele (5, Ele (2, Ele (1, Empty))))
 
このように入れ子にしてどんどん整数を並べていくことができます。
 
このように、discreminated unionで、一部に定義する型自身を含む定義法を「Recursive Type Definitions (再帰的型定義)」と呼びます。
 
これは、とても便利な定義方法で、F#で、リスト構造や、ツリー構造などを扱うときによく使われます。
 
実際に上で定義したのは、「リスト構造」の内の一つの実装例の一つです。
 
一般にリスト構造といえば、電車のように、車両がつながっているというイメージですが、上の定義では、
どんどん「整数値を保持する皮をかぶせていく」というイメージになっています。
 
それでは、myList型を対象として、リストチック(?)な関数を定義してみましょう。
 
まずは、一番外側(先頭?)の要素を取り出す関数です。(Emptyのときは例外を投げるものとします。)
 
> let rec myHead mlst =
    match mlst with
    |Empty
        -> failwith "要素がありません"
    |Ele(v,rest)
        -> v;;
 
val myHead : myList -> int
 
使用例
> myHead t3;;
val it : int = 5
 
(問題)
一番外側(先頭?)の要素を取り出した残りを返す関数myTailを定義してみてください。(Emptyのときは例外を投げるものとします。)
 
(解答例)
> let rec myTail mlst =
    match mlst with
    |Empty
        -> failwith "要素がありません"
    |Ele(v,rest)
        ->rest;;
 
val myTail : myList -> myList
 
> myTail t4;;
val it : myList = Ele (5, Ele (2, Ele (1, Empty)))
 
> myTail t1;;
val it : myList = Empty

 
 
次は、保持した値をすべて表示する関数です。
 
> let rec dispAll mlst =
    match mlst with
    |Empty
        -> ()
    |Ele(v,rest)
        -> printfn "%A" v
           dispAll rest  ;;
 
val dispAll : myList -> unit
 
実行例
> dispAll t4;;
7
5
2
1
val it : unit = ()
 
これを一般化すればList.iter風の関数が出来上がります。
 
> let rec myIter f mlst =
    match mlst with
    |Empty
        -> ()
    |Ele(v,rest)
        -> f v
           myIter f rest  ;;
 
val myIter : (int -> unit) -> myList -> unit
 
使用例
 
> myIter (fun i -> printfn "%d" i) t4;;
7
5
2
1
val it : unit = ()
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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