Previous Up Next

Chapter 6  ¥ì¥³¡¼¥É·¿/¥ô¥¡¥ê¥¢¥ó¥È·¿¤È¤½¤Î±þÍÑ

¥ì¥³¡¼¥É·¿¤ä¥ô¥¡¥ê¥¢¥ó¥È·¿¤Ï¡¤ÁÈ·¿¡¤¥ê¥¹¥È·¿¤ÈƱÍͤˡ¤¤½¤Î¤è¤¦¤Ê̾Á°¤Î°ì¤Ä ¤Î·¿¤¬Â¸ºß¤¹¤ë¤ï¤±¤Ç¤Ï¤Ê¤¯¡¤¹½Â¤¤Î¤¢¤ë¥Ç¡¼¥¿¤òƳÆþ¤¹¤ë¤¿¤á¤Î¡¤»÷¤¿¤è¤¦ ¤Ê¹½Â¤¤ò»ý¤Ã¤¿·¿¤Î¼ïÎà¤Ç¤¢¤ë¡¥¥ì¥³¡¼¥É¤ÏÁȤÈƱÍͤˤ¤¤¯¤Ä¤«¤Î Ãͤòʤ٤뤳¤È¤Ç¹½À®¤µ¤ì¤ë¥Ç¡¼¥¿¤Ç¤¢¤ë¤Î¤ËÂФ·¡¤ ¥ô¥¡¥ê¥¢¥ó¥È¤Ï°Û¤Ê¤ë¼ïÎà¤ÎÃͤòƱ¤¸·¿¤ÎÃͤȤ·¤Æº®¤¼¤Æ°·¤¦¤¿¤á¤Î¤â¤Î¤Ç¤¢¤ë¡¥ ¤³¤ì¤é¤Ï¡¤¤½¤ì¤¾¤ì C ¸À¸ì¤Î¹½Â¤ÂÎ(struct)¤È¶¦ÍÑÂÎ(union)¤Ë¶á¤¤¡¥ ¤Þ¤¿¡¤¥ô¥¡¥ê¥¢¥ó¥È·¿¤Ï¥ê¥¹¥È¤Ê¤É¤ÎºÆµ¢Åª¤Ê¹½Â¤¤ò»ý¤Ä¥Ç¡¼¥¿¹½Â¤¤òƳÆþ¤¹¤ë¤¿¤á ¤Ë»È¤ï¤ì¤ë¡¥¤É¤Á¤é¤â¡¤»ÈÍѤ¹¤ë¤¿¤á¤Ë¤Ï¥×¥í¥°¥é¥Þ¤¬¶ñÂÎŪ¤Ê·¿¤Î¹½Â¤¤òÀë¸À¤ò¤¹¤ë ɬÍפ¬¤¢¤ë¡¥ÌäÂêÎΰè¤Ë±þ¤¸¤ÆŬÀڤʥǡ¼¥¿·¿¤ò¥Ç¥¶¥¤¥ó¡¦ÄêµÁ¤¹¤ë¤³¤È¤Ï (Objective Caml¤Ë¸Â¤é¤º)¥×¥í¥°¥é¥ß¥ó¥°¤Ë¤ª¤¤¤ÆÈó¾ï¤Ë½ÅÍפʵ»½Ñ¤Ç¤¢¤ë¡¥

6.1  ¥ì¥³¡¼¥É·¿

¥ì¥³¡¼¥É·¿¤ÎÃͤϡ¤ÁȤÈƱÍͤˡ¤ËܼÁŪ¤Ë¤ÏÃͤò¤¤¤¯¤Ä¤«Ê¤٤¿¤â¤Î¤Ç¤¢¤ë¡¥ ÁȤȤΰ㤤¤Ï¡¤¤½¤ì¤¾¤ì¤ÎÍ×ÁǤË̾Á°¤òÍ¿¤¨¤Æ¡¤¤½¤Î̾Á°¤Ç¥ì¥³¡¼¥É¤ÎÍ×ÁÇ ¤Ë¥¢¥¯¥»¥¹¤Ç¤­¤ë¤³¤È¤Ç¤¢¤ë¡¥¤³¤Î̾Á°¤ÈÃͤÎÁȤò¥Õ¥£¡¼¥ë¥É(field)¡¤ ¥Õ¥£¡¼¥ë¥É¤Î̾Á°¤ò¥Õ¥£¡¼¥ë¥É̾¡¤¤È¸Æ¤Ö¡¥

Î㤨¤Ð¡¤³ØÀ¸¤Î¥Ç¡¼¥¿¥Ù¡¼¥¹¤òºî¤ë¤³¤È¤ò¹Í¤¨¤è¤¦¡¥³ØÀ¸°ì¿Í°ì¿Í¤Î¥Ç¡¼¥¿¤Ï ̾Á°¤òɽ¤¹ name ¥Õ¥£¡¼¥ë¥É¡¤³ØÀ¸¾ÚÈÖ¹æ¤òɽ¤¹ id ¥Õ¥£¡¼¥ë¥É¤ÎÊÂ¤Ó¤È ¤¹¤ë¡¥¿·¤·¤¤¥ì¥³¡¼¥É·¿¤Ï¡¤type Àë¸À¤ò¤Ä¤«¤Ã¤ÆÄêµÁ¤¹¤ë¤³¤È¤¬¤Ç¤­¤ë¡¥

# type student = {name : string; id : int};;
type student =  name : string; id : int; 

student ¤¬¿·¤·¤¤·¿¤Î¼±Ê̻ҤǤ¢¤ë¡¥°ìÈÌŪ¤Ë¤Ï¡¤ ³Æ¥Õ¥£¡¼¥ë¥É¤Ë³ÊǼ¤µ¤ì¤ëÃͤη¿¤ò¥Õ¥£¡¼¥ë¥É̾¤È¤È¤â¤Ëʤ١¤{} ¤Ç °Ï¤à¤³¤È¤Ç¥ì¥³¡¼¥É·¿¤ò¼¨¤¹¡¥

type ⟨ ·¿Ì¾ ⟩ = {⟨ ¥Õ¥£¡¼¥ë¥É̾1 ⟩ : ⟨ ·¿1 ⟩; ...; ⟨ ¥Õ¥£¡¼¥ë¥É̾n ⟩ : ⟨ ·¿n ⟩}

ÄêµÁ¤µ¤ì¤¿¥ì¥³¡¼¥É¤ÎÃͤϡ¤

{⟨ ¥Õ¥£¡¼¥ë¥É̾1 ⟩ = ⟨ ¼°1 ⟩; ...; ⟨ ¥Õ¥£¡¼¥ë¥É̾n ⟩ = ⟨ ¼°n ⟩}

¤Ç¹½À®¤¹¤ë¤³¤È¤¬¤Ç¤­¤ë¡¥1

# let st1 = {name = "Taro Yamada"; id = 123456};;
val st1 : student = name = "Taro Yamada"; id = 123456

¥ì¥³¡¼¥É¤ÎÍ×ÁǤϡ¤ÁȤÈƱÍͤ˥ѥ¿¡¼¥ó¥Þ¥Ã¥Á¤Ç¥¢¥¯¥»¥¹¤¹¤ë ÊýË¡¤È¡¤¥Õ¥£¡¼¥ë¥É¤Ò¤È¤Ä¤ÎÃͤΤߤò¥É¥Ã¥Èµ­Ë¡¤È¸Æ¤Ð¤ì¤ëÊýË¡¤Ç ¥¢¥¯¥»¥¹¤¹¤ëÊýË¡¤¬¤¢¤ë¡¥¥ì¥³¡¼¥É¥Ñ¥¿¡¼¥ó¤Ï¡¤

{⟨ ¥Õ¥£¡¼¥ë¥É̾1 ⟩ = ⟨ ¥Ñ¥¿¡¼¥ó1 ⟩; ...; ⟨ ¥Õ¥£¡¼¥ë¥É̾n ⟩ = ⟨ ¥Ñ¥¿¡¼¥ón ⟩}

¤È¤¤¤¦·Á¤Çɽ¤µ¤ì¤ë¡¥

# let string_of_student {name = n; id = i} = n ^ "'s ID is " ^ string_of_int i;;
val string_of_student : student -> string = <fun>
# string_of_student st1;;
- : string = "Taro Yamada's ID is 123456"

¤Þ¤¿¤Ï ⟨ ¥ì¥³¡¼¥É ⟩.⟨ ¥Õ¥£¡¼¥ë¥É̾ ⟩ ¤È¤¤¤¦·Á¤Ç ⟨ ¥ì¥³¡¼¥É ⟩¤«¤é⟨ ¥Õ¥£¡¼¥ë¥É̾ ⟩¤ËÂбþ¤¹¤ëÍ×ÁǤò¼è¤ê½Ð¤¹¤³¤È¤¬ ¤Ç¤­¤ë¡¥

# let string_of_student st = st.name ^ "'s ID is " ^ string_of_int st.id;;
val string_of_student : student -> string = <fun>

¤Þ¤¿¥ì¥³¡¼¥É¤Î°ìÉô¤Î¥Õ¥£¡¼¥ë¥É¤òÊѹ¹¤·¤¿¤À¤±¤Î¿·¤·¤¤¥ì¥³¡¼¥É¤ò À¸À®¤·¤¿¤¤¾ì¹ç¤Ë¤Ï¡¤

{⟨ ¥ì¥³¡¼¥É¼° ⟩ with 
  ⟨ ¥Õ¥£¡¼¥ë¥É̾1 ⟩ = ⟨ ¼°1 ⟩; ...; ⟨ ¥Õ¥£¡¼¥ë¥É̾n ⟩ = ⟨ ¼°n ⟩}

¤È¤¤¤¦¼°¤Ç¤Ç¤­¤ë¡¥Ä¹¤¤¥ì¥³¡¼¥É¤Î°ìÉô¤À¤±Êѹ¹¤·¤¿¤¤¤È¤­¤ËÊØÍø¤Ç¤¢¤ë¡¥

# type teacher = {tname : string; room : string; ext : int};;
type teacher =  tname : string; room : string; ext : int; 
# let t1 = {tname = "Atsushi Igarashi"; room = "140"; ext = 4953};;
val t1 : teacher = tname = "Atsushi Igarashi"; room = "140"; ext = 4953
# let t2 = {t1 with room = "142"};;
val t2 : teacher = tname = "Atsushi Igarashi"; room = "142"; ext = 4953

¤³¤Î»þ¡¤µ¤¤ò¤Ä¤±¤Ê¤±¤ì¤Ð¤¤¤±¤Ê¤¤¤Î¤¬¡¤with ¤Ï¥Õ¥£¡¼¥ë¥É¤Î¹¹¿· ¤ò¹Ô¤¦¤Î¤Ç¤Ï¤Ê¤¯¡¤¿·¤·¤¤¥ì¥³¡¼¥É¤òÀ¸À®¤·¤Æ¤¤¤ë¤È¤¤¤¦¤³¤È¤Ç¤¢¤ë¡¥t1 ¤¬Â«Çû ¤µ¤ì¤¿¥ì¥³¡¼¥É¤Î room ¥Õ¥£¡¼¥ë¥É¤ÎÃÍ¤Ï t2 ¤ÎÄêµÁ¸å¤âÊѤäƤ¤¤Ê¤¤¡¥ ¤Ä¤Þ¤ê¡¤

# t1;;
- : teacher = tname = "Atsushi Igarashi"; room = "140"; ext = 4953

t1 ¤ÎÃͤÏt2¤ÎÄêµÁÁ°¸å¤ÇÊѲ½¤·¤Ê¤¤¡¥

ÁÈ·¿¤È¥ì¥³¡¼¥É·¿¤Î°ã¤¤¤Ë¤Ä¤¤¤Æ

¥ì¥³¡¼¥É·¿¤¬ÁÈ·¿¤È°ã¤¦ÅÀ¤Ï¡¤³ÆÍ×ÁǤË̾Á°¤¬¤Ä¤­¡¤¤½¤Î̾Á°¤Ç¥Ñ¥¿¡¼¥ó¥Þ¥Ã¥Á¤ò ²ð¤µ¤ºÍ×ÁǤ˥¢¥¯¥»¥¹¤Ç¤­¤ë¤³¤È¡¤°ìÉô¤ÎÍ×ÁǤÀ¤±¤òÊѹ¹¤·¤¿¥ì¥³¡¼¥É¤òÍÆ°× ¤Ëºî¤ë¤³¤È¤¬¤Ç¤­¤ë¤³¤È¤Î¾¤Ë¡¤·¿Àë¸À¤ò¤·¤Ê¤¤¤È»È¤¨¤Ê¤¤¤È¤¤¤¦¤³¤È¤¬¤¢¤ë¡¥ ¤Þ¤¿¡¤¥ì¥³¡¼¥É·¿¤Ï¾ï¤Ë̾Á°¤Ç»²¾È¤µ¤ì¡¤{...} ¤È¤¤¤¦É½¸½¤Ï·¿¤½¤Î¤â¤Î¤È¤·¤Æ¤Ï »È¤¨¤Ê¤¤¡¥¤Ä¤Þ¤ê¡¤°ú¿ô¤Î·¿¤È¤·¤Æ

let f (x : {name : string; id : int}) = ...

¤È¤·¤¿¤ê¡¤Æþ¤ì»Ò¤Ë¤Ê¤Ã¤¿¥ì¥³¡¼¥É¤òÀë¸À¤¹¤ë¤Î¤Ë¡¤

type student_teacher = 
  {s : {name : string; id : int}; 
   t : {tname : string; room : string; ext : int}};;

¤ÈÀë¸À¤¹¤ë¤³¤È¤Ï¤Ç¤­¤Ê¤¤¡¥Àµ¤·¤¯¤ÏÆ⦤Υ쥳¡¼¥É·¿¤òÀë¸À¤·¤Æ¤ª¤¤¤Æ¡¤

# type student_teacher = {s : student; t : teacher};;
type student_teacher =  s : student; t : teacher; 

¤È¹Ô¤¦¡¥¤¿¤À¤·¡¤¥Í¥¹¥È¤·¤¿¥ì¥³¡¼¥É¤ÎÃͤä¥Ñ¥¿¡¼¥ó¤ÏľÀܹ½À®²Äǽ¤Ç¤¢¤ë¡¥

# let st = {s = {name = "Taro Yamada"; id = 123456}; t = t1};;
val st : student_teacher =
s = name = "Taro Yamada"; id = 123456;
t = tname = "Atsushi Igarashi"; room = "140"; ext = 4953
·¿Ì¾/¥Õ¥£¡¼¥ë¥É̾¤Ë¤Ä¤¤¤Æ¤ÎÃí°Õ¡¦Ì¾Á°¶õ´Ö¤Ë¤Ä¤¤¤Æ

·¿Ì¾¡¦¥Õ¥£¡¼ ¥ë¥É̾¤Ë»ÈÍѤǤ­¤ë¤Î¤ÏÊÑ¿ô̾¤Ë»ÈÍѤǤ­¤ë¤Î¤ÈƱÍͤÊʸ»úÎó¤Ç¤¢¤ë¡¥¥Õ¥£¡¼¥ë¥É ̾¤Ï type Àë¸À¤Ç¥ì¥³¡¼¥É·¿¤òÀë¸À¤¹¤ë¤³¤È¤Ç¡¤¤Ï¤¸¤á¤Æ»ÈÍѤ¹¤ë¤³¤È¤¬¤Ç¤­¤ë¡¥ Ʊ¤¸¥Õ¥£¡¼¥ë¥É̾¤ò»ý¤ÄÊ̤η¿¤òÀë¸À¤¹¤ë¤È¡¤ÊÑ¿ô¤ÎºÆÀë¸À¤ÈƱÍÍ¡¤¸Å¤¤¥Õ¥£¡¼¥ë ¥É̾¤ÎÄêµÁ¤Ï±£¤µ¤ì¤Æ¤·¤Þ¤¦¤Î¤ÇÃí°Õ¤¬É¬ÍפǤ¢¤ë¡¥¤Ä¤Þ¤ê¡¤

# type foo = {name : bool};;
type foo =  name : bool; 

¤Ê¤É¤È name ¥Õ¥£¡¼¥ë¥É¤ò»ý¤ÄÊ̤Υ쥳¡¼¥É·¿¤òÀë¸À¤·¤Æ¤·¤Þ¤¦¤È¡¤¿·¤¿¤Ë student ¤ÎÃͤò¹½À®¤·¤¿¤ê¡¤name ¥Õ¥£¡¼¥ë¥É¤Ë¥¢¥¯¥»¥¹¤Ê¤É¤¬¤Ç¤­¤Ê¤¯ ¤Ê¤Ã¤Æ¤·¤Þ¤¦¡¥

# {name = "Ichiro Suzuki"; id = 51};;
 name = "Ichiro Suzuki"; id = 51;;
^^^^^^^^^^^^^^^
This expression has type string but is here used with type bool
# st1.name;;
 st1.name;;
^^^
This expression has type student but is here used with type foo

¤¿¤À¤·¡¤ÊÑ¿ô̾¡¤¥Õ¥£¡¼¥ë¥É̾¡¤·¿Ì¾¤ÏÊ̤Î̾Á°¶õ´Ö(name space)¤Ë°¤· ¤Æ¤¤¤ë¤Î¤Ç¡¤Î㤨¤Ð¡¤Àë¸ÀºÑ¤Î¥Õ¥£¡¼¥ë¥É̾¤ÈƱ¤¸ÊÑ¿ô¤òÍѤ¤¤Æ¤â¡¤¥Õ¥£¡¼¥ë¥É̾¤¬ ±£¤µ¤ì¤¿¤ê¤¹¤ë¤³¤È¤Ï¤Ê¤¤¡¥

6.2  ¥ô¥¡¥ê¥¢¥ó¥È·¿

¥ô¥¡¥ê¥¢¥ó¥È·¿¤¬²¿¤«¤òÀâÌÀ¤¹¤ëÁ°¤Ë¡¤Æ°µ¡ÉÕ¤±¤ÎÎã¤È¤·¤Æ¡¤ ÍÍ¡¹¤Ê¿Þ·Á¤Î¥Ç¡¼¥¿¤ò°·¤¦¤³¤È¤ò¹Í¤¨¤Æ¤ß¤è¤¦¡¥°·¤¦¤Î¤Ï°Ê²¼¤Î4¼ïÎà¤Î¿Þ·Á ¤Ç¡¤¤½¤ì¤¾¤ì·Á¾õ¤ò·èÄꤹ¤ë¤¿¤á¤Î¥Ç¡¼¥¿¤ò¤â¤Ä¤È¤¹¤ë¡¥

¤³¤³¤Ç¡¤¤³¤Î¤è¤¦¤Ê¿Þ·Á¥Ç¡¼¥¿¤ò°·¤ª¤¦¤È¤¹¤ë¤È¡¤

¤È¤¤¤¦ÌäÂ꤬¤¢¤ë¡¥¥ô¥¡¥ê¥¢¥ó¥È·¿¤Ï¤³¤Î¤è¤¦¤Ë¡¤°Û¤Ê¤ë¥Ç¡¼¥¿(ɽ¸½¤¬Æ±¤¸¤Ç¤â °ÕÌ£¤¬°Û¤Ê¤ë¾ì¹ç¤â´Þ¤á¤Æ)¤òº®¤¼¤Æ¡¤°ì¤Ä¤Î·¿¤È¤·¤Æ°·¤¤¤¿¤¤ºÝ¤Ë»È¤¦¤â¤Î¤Ç¡¤¤Ò ¤È¤Ä¤Ò¤È¤Ä¤ÎÃͤϡ¤¥Ç¡¼¥¿¤ÎËÜÂÎ((2, 4) ¤ä 8 ¤Ê¤É)¤Ë¡¤¤½¤Î¥Ç¡¼¥¿¤Ï¤Ê¤Ë¤ò ɽ¤¹¤¿¤á¤Î¤â¤Î¤«(±ß¡¤Ä¹Êý·Á¡¤ÀµÊý·Á)¤Î¾ðÊó¤òÉղä·¤¿¤â¤Î¤Çɽ¤µ¤ì¤ë¡¥

¤Ç¤Ï¡¤¿Þ·Á¤òɽ¤¹¥ô¥¡¥ê¥¢¥ó¥È·¿¤òÄêµÁ¤·¤Æ¤ß¤è¤¦¡¥

# type figure = 
    Point 
  | Circle of int 
  | Rectangle of int * int 
  | Square of int;;
type figure = Point | Circle of int | Rectangle of int * int | Square of int

¥ô¥¡¥ê¥¢¥ó¥È·¿¤â¥ì¥³¡¼¥É·¿¤ÈƱÍÍ type ¤ò»È¤Ã¤ÆÀë¸À¤¹¤ë¡¥figure ¤Ï¿·¤·¤¤·¿¤Î̾Á°¤Ç¤¢¤ë¡¥Point, Circle, Rectangle, Square ¤Ï¥³¥ó¥¹¥È¥é¥¯¥¿(constructor)¤È¸Æ¤Ð¤ì¡¤¾å¤Ç½Ò¤Ù¤¿¡Ö¤½¤Î¥Ç¡¼ ¥¿¤Ï²¿¤òɽ¤¹¤¿¤á¤Î¤â¤Î¤«¡×¤È¤¤¤¦¾ðÊó¤ËÁêÅö¤¹¤ë¡¥of ¤Î¸å¤Ë¤Ï¡¤¥³¥ó¥¹ ¥È¥é¥¯¥¿¤¬Éղ䵤ì¤ëÃͤη¿¤òµ­½Ò¤¹¤ë¡¥ of °Ê²¼¤Ï¾Êά²Äǽ¤Ç¡¤¾Êά¤·¤¿ ¾ì¹ç¥³¥ó¥¹¥È¥é¥¯¥¿Ã±ÆȤǤ½¤Î·¿¤ÎÃͤȤʤ롥(¤³¤ÎÎã¤Ç¤Ï¡¤ÅÀƱ»Î¤Ï ¶èÊ̤¹¤ëɬÍפ¬¤Ê¤¤¤Î¤Ç0°ú¿ô¥³¥ó¥¹¥È¥é¥¯¥¿¤È¤·¤ÆÀë¸À¤·¤Æ¤¤¤ë¡¥) ¥ô¥¡¥ê¥¢¥ó¥È·¿¤ÎÃͤϡ¤¥³¥ó¥¹¥È¥é¥¯¥¿¤ò´Ø¿ô¤Î¤è¤¦¤ËÂбþ¤¹¤ë·¿¤ÎÃÍ¤Ë ¡ÖŬÍѡפ¹¤ë¤³¤È¤Ë¤è¤Ã¤Æ¹½À®¤µ¤ì¤ë¡¥

# let c = Circle 3;;
val c : figure = Circle 3
# let figs = [Point; Square 5; Rectangle (4, 5)];;
val figs : figure list = [Point; Square 5; Rectangle (4, 5)]

¼¡¤Ë¡¤Í¿¤¨¤é¤ì¤¿¿Þ·Á¤ÎÌÌÀѤòµá¤á¤ë´Ø¿ô¤ò¹Í¤¨¤Æ¤ß¤è¤¦¡¥¤Þ¤º¤Ï¡¤¿Þ·Á¤¬ ¤É¤Î¼ïÎà¤Î¤â¤Î¤Ç¤¢¤ë¤«¤òÄ´¤Ù¤Æ¡¤¤½¤ì¤Ë¤è¤Ã¤Æ¾ì¹ç¤ï¤±¤ò¤¹¤ëɬÍפ¬¤¢¤ë¡¥ ¤³¤Î¾ì¹ç¤ï¤±¤Ï match¼°¤Ç¹Ô¤¦¤³¤È¤¬¤Ç¤­¤ë¡¥¥ô¥¡¥ê¥¢¥ó¥È·¿¤ÎÃͤËÂФ¹¤ë ¥Ñ¥¿¡¼¥ó¤Ï

⟨ ¥³¥ó¥¹¥È¥é¥¯¥¿ ⟩ ⟨ ¥Ñ¥¿¡¼¥ó ⟩

¤È¤¤¤¦·Á¤Ç¡¤¥³¥ó¥¹¥È¥é¥¯¥¿¤¬Å¬ÍѤµ¤ì¤¿Ãͤ¬⟨ ¥Ñ¥¿¡¼¥ó ⟩¤Ë ¥Þ¥Ã¥Á¤¹¤ë¤³¤È¤Ë¤Ê¤ë¡¥⟨ ¥Ñ¥¿¡¼¥ó ⟩¤¬¾Êά¤µ¤ì¤¿¾ì¹ç¤Ë¤Ï °ú¿ô¤Î¤Ê¤¤¥³¥ó¥¹¥È¥é¥¯¥¿¤Ë¥Þ¥Ã¥Á¤¹¤ë¤³¤È¤Ë¤Ê¤ë¡¥

# let area = function
      Point -> 0
    | Circle r -> r * r * 3  (* elementary school approximation :-) *)
    | Rectangle (lx, ly) -> lx * ly
    | Square l -> l * l;;
val area : figure -> int = <fun>

°ú¿ô¤ËÂФ·¤¹¤°¤Ë¥Þ¥Ã¥Á¥ó¥°¤ò¹Ô¤¦¤Î¤Ç¡¤function ¤ò»ÈÍѤ·¤Æ¤¤¤ë¡¥(Âè5¾Ï»²¾È)

# area c;;
- : int = 27
# map area figs;;
- : int list = [0; 25; 20]
¤½¤Î¾¤Î¥Ñ¥¿¡¼¥ó

¥ô¥¡¥ê¥¢¥ó¥È·¿¤ËÂФ¹¤ë¥Ñ¥¿¡¼¥ó¥Þ¥Ã¥Á¤Ç¤Ï¡¤´ðËÜŪ¤Ë¥³¥ó¥¹¥È¥é¥¯¥¿¤Î ¿ô¤À¤±¾ì¹çʬ¤±¤ò¤«¤«¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¤¬¡¤¤¤¤¯¤Ä¤«¤Î¾ì¹ç¤Ç½èÍý¤¬ ¶¦Ä̤·¤Æ¤¤¤ë¾ì¹ç¤Ë¤Ï or ¥Ñ¥¿¡¼¥ó ¤È¸Æ¤Ð¤ì¤ë¥Ñ¥¿¡¼¥ó¤Ç ¤Þ¤È¤á¤ë¤³¤È¤¬¤Ç¤­¤ë¡¥¼¡¤Î´Ø¿ô¤Ï¡¤Í¿¤¨¤é¤ì¤¿¿Þ·Á¤ò°Ï¤à¤³¤È¤¬¤Ç¤­¤ë ÀµÊý·Á¤òÊÖ¤¹´Ø¿ô¤Ç¤¢¤ë¡¥(ĹÊý·Á¤ÏºÇ½é¤ÎÊÕ¤¬Ã»ÊդȲ¾Äꤹ¤ë¡¥)

# let enclosing_square = function
      Point -> Square 1
    | Circle r -> Square (r * 2)
    | Rectangle (_, l) | Square l -> Square l;;
val enclosing_square : figure -> figure = <fun>

Rectangle (_, l) | Square l ¤¬ or ¥Ñ¥¿¡¼¥ó¤È¸Æ¤Ð¤ì¤ë¤â¤Î¤Ç¡¤ °ìÈÌŪ¤Ë¤Ï

⟨ ¥Ñ¥¿¡¼¥ó1 ⟩ | ⟨ ¥Ñ¥¿¡¼¥ó2

¤È½ñ¤«¤ì¡¤¤É¤Á¤é¤«¤Ë¥Ñ¥¿¡¼¥ó¤Ë¥Þ¥Ã¥Á¤¹¤ë¤â¤Î¤¬Á´ÂΤ˥ޥåÁ¤¹¤ë¡¥ ³ÆÉôʬ¥Ñ¥¿¡¼¥ó¤ÇƳÆþ¤µ¤ì¤ëÊÑ¿ô(·²)¤Ï¡¤ (¤É¤Á¤é¤Î¥Ñ¥¿¡¼¥ó¤Ë¥Þ¥Ã¥Á¤·¤Æ¤â-> °Ê¹ß¤Î½èÍý¤¬¤¦¤Þ¤¯¤¤¤¯¤è¤¦¤Ë) Ʊ¤¸Ì¾Á°/·¿¤Ç¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡¥

¤Þ¤¿¡¤Ê£¿ô¤ÎÃͤËÂФ·¤Æ¥Þ¥Ã¥Á¤ò¤È¤ë¤È¤­¤Ë¤ÏÁȤòÍøÍѤ·¤Æ ¥Þ¥Ã¥Á¤ò¤È¤ë¤Î¤¬¤è¤¤¡¥¼¡¤Î´Ø¿ô¤Ï¡¤Æó¤Ä¤Î¿Þ·Á¤¬Áê»÷¤Ç¤¢¤ë¤«¤ò ȽÄꤹ¤ë´Ø¿ô¤Ç¤¢¤ë¡¥or ¥Ñ¥¿¡¼¥ó¤È¡¤ÁȤÎÍøÍÑË¡¤ËÃí°Õ¡¥

# let similar x y = 
    match (x, y) with
      (Point, Point) | (Circle _, Circle _) | (Square _, Square _) -> true
    | (Rectangle (l1, l2), Rectangle (l3, l4)) -> (l3 * l2 - l4 * l1) = 0
    | _ -> false;;
val similar : figure -> figure -> bool = <fun>
# similar (Rectangle (2, 4)) (Rectangle (1, 2));;
- : bool = true
¥³¥ó¥¹¥È¥é¥¯¥¿¤Î̾Á°¤Ë¤Ä¤¤¤Æ

¥³¥ó¥¹¥È¥é¥¯¥¿¤Î̾Á°¤Ï¡¤ÊÑ¿ô̾¡¤·¿Ì¾¤È°ã¤Ã¤Æ¡¤°ìʸ»úÌܤ¬±ÑÂçʸ»ú¤Ç¤Ê¤±¤ì¤Ð ¤Ê¤é¤Ê¤¤¡¥¤è¤êÀµ³Î¤Ë¤Ï

  1. °ìʸ»úÌܤ¬±ÑÂçʸ»ú¤Ç¡¤
  2. Æóʸ»úÌܰʹߤϱѿô»ú(A...Z, a...z, 0...9)¡¤¥¢¥ó¥À¡¼¥¹¥³¥¢¤Þ¤¿¤Ï ¥×¥é¥¤¥à (')

¤Ç¤¢¤ë¤è¤¦¤ÊǤ°Õ¤ÎŤµ¤Îʸ»úÎó¤Ç¤¢¤ë¡¥

¥³¥ó¥¹¥È¥é¥¯¥¿¤â¥ì¥³¡¼¥É·¿¤Î¥Õ¥£¡¼¥ë¥É̾¤ÈƱ¤¸¤è¤¦¤Ë¡¤Æ±¤¸Ì¾Á°¤Î¤â¤Î¤ò ºÆÀë¸À¤·¤Æ¤·¤Þ¤¦¤È¡¤Á°¤ËÄêµÁ¤µ¤ì¤¿¥³¥ó¥¹¥È¥é¥¯¥¿¤òȼ¤¦·¿¤Ï»È¤¤Êª¤Ë ¤Ê¤é¤Ê¤¯¤Ê¤Ã¤Æ¤·¤Þ¤¦¤Î¤ÇÃí°Õ¤¹¤ë¤³¤È¡¥

6.3  ¥ô¥¡¥ê¥¢¥ó¥È·¿¤Î±þÍÑ

Îóµó·¿

Pascal, C, C++ ¤ÎÎóµó·¿(enum ·¿)¤Ï°ú¿ô¤ò¼è¤é¤Ê¤¤¥³¥ó¥¹¥È ¥é¥¯¥¿¤À¤±¤«¤é¤Ê¤ë¥ô¥¡¥ê¥¢¥ó¥È·¿¤Çɽ¸½¤¹¤ë¤³¤È¤¬¤Ç¤­¤ë¡¥

# type color = Black | Blue | Red | Magenta | Green | Cyan | Yellow | White;;
type color = Black | Blue | Red | Magenta | Green | Cyan | Yellow | White

enum ¤ÎÃͤ¬¼Â¤ÏÀ°¿ô¤Ç¤·¤«¤Ê¤¤ C ¤È¤Ï°ã¤¤¡¤¥³¥ó¥¹¥È¥é¥¯¥¿Æ±»Î¤Î­¤·»»¤Ê¤É¤Ï ÅöÁ³ÄêµÁ¤µ¤ì¤Ê¤¤¡¥(¤½¤¦¤¤¤¦´Ø¿ô¤ò½ñ¤«¤Ê¤¤¸Â¤ê¡¥)¤³¤Î·¿¾å¤Î´Ø¿ô¤Ï 8¤Ä¤Î¾ì¹ç¤ï¤±¤ò¹Ô¤ï¤Ê¤±¤ì¤Ð¤¤¤±¤Ê¤¤¡¥

# let reverse = function
      Black -> White | Blue -> Yellow | Red -> Cyan | Magenta -> Green
    | Green -> Magenta | Cyan -> Red | Yellow -> Blue | White -> Black;;
val reverse : color -> color = <fun>

bool·¿¤âÎóµó·¿¤Î°ì¼ï¤È¸«¤Ê¤¹¤³¤È¤¬¤Ç¤­¤ë¡¥

type bool = true | false

¤½¤·¤Æ¡¤if¼°¤Ï match¼°¤ÎÊÑ·Á¤È¸«¤Ê¤¹¤³¤È¤¬¤Ç¤­¤ë¡¥

if ⟨ ¼°1 ⟩ then ⟨ ¼°2 ⟩ else ⟨ ¼°3 ⟩
∼ match ⟨ ¼°1 ⟩ with true -> ⟨ ¼°2 ⟩ | false -> ⟨ ¼°3

¥³¥ó¥¹¥È¥é¥¯¥¿¤Î̾Á°¤ÎÀ©¸Â¤Ê¤É¤â¤¢¤ë¤¿¤á¡¤¾å¤Î type Àë¸À¤ò¼ÂºÝ¤Ë¹Ô¤Ê ¤¦¤³¤È¤Ï¤Ç¤­¤Ê¤¤¤¬¡¤bool·¿¤â³µÇ°Åª¤Ë¤Ï¥ô¥¡¥ê¥¢¥ó¥È·¿¤Î°ì¼ï¤È¹Í¤¨¤ë¤Î ¤ÏÍý²ò¤Î½õ¤±¤Ë¤Ê¤ë¤À¤í¤¦¡¥

ºÆµ¢¥ô¥¡¥ê¥¢¥ó¥È·¿

¥ô¥¡¥ê¥¢¥ó¥È·¿¤Ï of °Ê²¼¤Ëº£Àë¸À¤·¤è¤¦¤È¤·¤Æ¤¤¤ë·¿Ì¾¤ò»²¾È¤¹¤ë¤³¤È¤Ç ºÆµ¢Åª¤Ê¥Ç¡¼¥¿·¿¤òÄêµÁ¤¹¤ë¤³¤È¤â²Äǽ¤Ç¤¢¤ë¡¥¤³¤³¤Ç¤Ï¡¤¤â¤Ã¤È¤âñ½ã¤ÊºÆ µ¢Åª¥Ç¡¼¥¿¤ÎÎã¤È¤·¤Æ¡¤¼«Á³¿ô¤òɽ¤¹·¿¤ò¹Í¤¨¤Æ¤ß¤è¤¦¡¤¼«Á³¿ô¤Ï°Ê²¼¤Î¤è¤¦ ¤ËºÆµ¢Åª¤ËÄêµÁ¤Ç¤­¤ë¡¥

¡Ö¥¼¥í¡×¡Ö1Â礭¤¤¡×¤È¤¤¤¦Éôʬ¤ò¥³¥ó¥¹¥È¥é¥¯¥¿¤È¤·¤Æ¹Í¤¨¤ë¤È¼¡¤Î¤è¤¦¤Ê ·¿ÄêµÁ¤¬Æ³¤«¤ì¤ë¡¥

# type nat = Zero | OneMoreThan of nat;;
type nat = Zero | OneMoreThan of nat
# let zero = Zero and two = OneMoreThan (OneMoreThan Zero);;
val zero : nat = Zero
val two : nat = OneMoreThan (OneMoreThan Zero)

¤³¤Î¼«Á³¿ô¾å¤Ç¤Î²Ã»»¤Ï¡¤¥Ç¡¼¥¿¼«ÂΤκƵ¢ÅªÄêµÁ¤Ë½¾¤Ã¤Æ¡¤

¤ÈÄêµÁ¤Ç¤­¤ë¡¥

# let rec add m n = 
    match m with Zero -> n | OneMoreThan m' -> OneMoreThan (add m' n);;
val add : nat -> nat -> nat = <fun>
# add two two;;
- : nat = OneMoreThan (OneMoreThan (OneMoreThan (OneMoreThan Zero)))

¼Â¤Ï¡¤¤³¤Î¹½Â¤¤Ï¤è¤¯¸«¤Æ¤ß¤ë¤È¡¤¥ê¥¹¥È¤ËÎɤ¯»÷¤Æ¤¤¤ë¤³¤È¤Ëµ¤¤Å¤¯¡¥ ÃúÅÙ Zero ¤Ï¶õ¥ê¥¹¥È []¡¤OneMoreThan ¤Ï cons ¤ËÂбþ¤·¤Æ¤¤¤ë¡¥ ËܼÁŪ¤Ê°ã¤¤¤Ï³ÊǼ¤Ç¤­¤ëÍ×ÁǤÎ̵ͭ¤À¤±¤Ç¤¢¤ë¡¥nat ¤Î¹½Â¤¤ò ³ÈÄ¥¤¹¤ì¤Ð¡¤Î㤨¤Ð¡¤À°¿ô¥ê¥¹¥È¤òɽ¸½¤¹¤ë·¿¤ò´Êñ¤ËÄêµÁ¤¹¤ë¤³¤È¤¬¤Ç¤­¤ë¡¥

# type intlist = INil | ICons of int * intlist;;
type intlist = INil | ICons of int * intlist

(¿ÁêŪ¤Ê¥ê¥¹¥È¤ÎÄêµÁ¤Ï²¼¤Ç¹Ô¤¦¡¥)

¤Þ¤¿¥ô¥¡¥ê¥¢¥ó¥È·¿ÄêµÁ¤Ï¤Õ¤¿¤Ä¤Î·¿ÄêµÁ¤ò and ¤Ç·ë¤Ö¤³¤È¤Ë¤è¤Ã¤Æ¡¤Áê¸ßºÆµ¢Åª¤Ë¤¹¤ë¤³¤È¤â²Äǽ¤Ç¤¢¤ë¡¥ ²¼¤ÎÎã¤Ï¡¤¼Â¿ô¤Èʸ»úÎ󤬸ò¸ß¤Ë¸½¤ì¤ë¥ê¥¹¥È¤òɽ¸½¤·¤¿¤â¤Î¤Ç¤¢¤ë¡¥

# type fl_str_list = FNil | FCons of float * str_fl_list
  and str_fl_list = SNil | SCons of string * fl_str_list;;
type fl_str_list = FNil | FCons of float * str_fl_list
and str_fl_list = SNil | SCons of string * fl_str_list
# let fslist = FCons (3.14, SCons ("foo", FCons (2.7, SNil)));;
val fslist : fl_str_list = FCons (3.14, SCons ("foo", FCons (2.7, SNil)))

¤³¤Î·¿¾å¤Î´Ø¿ô¤Ï¼«Á³¤ËÁê¸ßºÆµ¢¤ÎÆó¤Ä¤Î´Ø¿ô¤ÇÄêµÁ¤µ¤ì¤ë¡¥¼¡¤Î´Ø¿ô¤Ï¡¤¤³¤Î2 ¼ïÎà¤Î¥ê¥¹¥È(¼Â¿ô¤«¤é»Ï¤Þ¤ë¤â¤Î¤È¡¤Ê¸»úÎ󤫤é»Ï¤Þ¤ë¤â¤Î)¤ÎŤµ¤ò·×»»¤¹¤ë ´Ø¿ô¤Ç¤¢¤ë¡¥

# let rec length_fs = function
      FNil -> 0
    | FCons (_, rest_sf) -> 1 + length_sf rest_sf
  and length_sf = function
      SNil -> 0
    | SCons (_, rest_fs) -> 1 + length_fs rest_fs;;
val length_fs : fl_str_list -> int = <fun>
val length_sf : str_fl_list -> int = <fun>
# length_fs fslist;;
- : int = 3
¿ÁêŪ¥ô¥¡¥ê¥¢¥ó¥È·¿

intlist ¤ÈƱÍͤˤ·¤Æ¡¤stringlist ¤Ê¤É¤òÄêµÁ¤·¤Æ¤æ¤¯¤È¡¤ ÄêµÁ¤¬¹ó»÷¤·¤Æ¤¤¤ë¤³¤È¤¬¤ï¤«¤ë¡¥·ë¶É¡¤

¤È¤¤¤¦¹½Â¤¤¬¶¦Ä̤·¤Æ¤¤¤ë¤¿¤á¤Ç¤¢¤ë¡¥¤Þ¤¿°ã¤¤¤ÏÍ×ÁǤη¿¤À¤±¤Ç¤¢¤ë¡¥ Objective Caml ¤Ç¤Ï¡¤Â¿Áê·¿´Ø¿ô¤¬¡¤(³µÇ°Åª¤Ë)´Ø¿ôÃæ¤Î·¿¾ðÊó¤ò¥Ñ¥é¥á¡¼¥¿²½¤¹¤ë¤³¤È¤Ç ÍÍ¡¹¤Ê·¿¤ÎÃͤËŬÍѤǤ­¤ë¤Î¤ÈƱÍÍ¡¤·¿ÄêµÁ¤Î°ìÉôʬ¤ò¥Ñ¥é¥á¡¼¥¿²½¤¹¤ë ¤³¤È¤â²Äǽ¤Ç¤¢¤ë¡¥¤¿¤À¤·¡¤´Ø¿ô¤È¤Ï°ã¤¤¡¤·¿¥Ñ¥é¥á¡¼¥¿¤òÌÀ¼¨Åª¤Ë ·¿Àë¸ÀÃæ¤Ë¼¨¤·¤Æ¤ä¤ëɬÍפ¬¤¢¤ë¡¥ ¿Áê·¿¥ê¥¹¥È¤Î·¿¤ò¥ô¥¡¥ê¥¢¥ó¥È·¿¤ÇÄêµÁ¤¹¤ë¤È¤¹¤ì¤Ð¡¤

# type 'a list = Nil | Cons of 'a * 'a list;;
type 'a list = Nil | Cons of 'a * 'a list

¤È¤¤¤Ã¤¿ÄêµÁ¤Ë¤Ê¤ë¡¥'a ¤¬·¿¥Ñ¥é¥á¡¼¥¿¤òɽ¤·¤Æ¤¤¤ë¡¥

¤½¤Î¾¡¤ÉÑÈˤ˻Ȥï¤ì¤ë¿ÁêŪ¥Ç¡¼¥¿·¿¤È¤·¤Æ¤Ï¡¤¥ª¥×¥·¥ç¥ó·¿¤È¤¤¤¦°Ê²¼¤ÇÄêµÁ ¤µ¤ì¤ë·¿¤¬¤¢¤ë¡¥

# type 'a option = None | Some of 'a;;
type 'a option = None | Some of 'a

ŵ·¿Åª¤Ë¤Ï None ¤¬Î㳰Ū¤Ê¡ÖÅú¤¨¤¬¤Ê¤¤¡×Ãͤòɽ¤·¡¤Àµ¾ï¤Ë·×»»¤¬¹Ô¤ï¤ì¤¿ ¾ì¹ç¤Ë Some v ¤È¤¤¤¦·Á¤Ç v ¤È¤¤¤¦Ãͤ¬Ê֤äƤ¯¤ë¡¥(Java, C ¤Ê¤É¤Ç¡¤null ¤â¤·¤¯¤Ï NULL ¤òÍѤ¤¤ÆÎ㳰Ū¤ÊÃͤò¼¨¤·¤Æ¤¤¤ë¤Î ¤È»÷¤Æ¤¤¤ë¡¥)¥ª¥×¥·¥ç¥ó·¿¤Ïocamlµ¯Æ°»þ¤ËÄêµÁºÑ¤Î·¿¤Ç¤¢¤ë¡¥

¥ô¥¡¥ê¥¢¥ó¥È·¿Àë¸À¤Î¤Þ¤È¤á

¥ô¥¡¥ê¥¢¥ó¥È·¿¤Ï¡¤°ìÈÌŪ¤Ë¤Ï°Ê²¼¤Î¤è¤¦¤Êʸˡ¤ÇÀë¸À¤µ¤ì¤ë¡¥[]¤Ç °Ï¤Þ¤ì¤¿Éôʬ¤Ï¾Êά²Äǽ¤Ç¤¢¤ë¡¥

type [⟨ ·¿ÊÑ¿ô11 ⟩ ⋯ ⟨ ·¿ÊÑ¿ô1k ⟩] ⟨ ·¿Ì¾1 ⟩ = 
    ⟨ ¥³¥ó¥¹¥È¥é¥¯¥¿11 ⟩ [of ⟨ ·¿11 ⟩] | ⋯ | ⟨ ¥³¥ó¥¹¥È¥é¥¯¥¿1n ⟩ [of ⟨ ·¿1l ⟩]
and [⟨ ·¿ÊÑ¿ô21 ⟩ ⋯ ⟨ ·¿ÊÑ¿ô1m ⟩] ⟨ ·¿Ì¾2 ⟩ = 
    ⟨ ¥³¥ó¥¹¥È¥é¥¯¥¿21 ⟩ [of ⟨ ·¿21 ⟩] | ⋯ | ⟨ ¥³¥ó¥¹¥È¥é¥¯¥¿2m ⟩ [of ⟨ ·¿2n ⟩]
and [⟨ ·¿ÊÑ¿ô3 ⟩ ⋯ ⟨ ·¿ÊÑ¿ô3p ⟩] ⟨ ·¿Ì¾3 ⟩ = ⋯
 ⋮

6.4  Case Study: ÆóʬÌÚ

ÌÚ(tree)¹½Â¤¤Ï¥ê¥¹¥È¡¤ÇÛÎó¤Ê¤É¤ÈʤÖÂåɽŪ¤Ê¥Ç¡¼¥¿¹½Â¤¤Ç ÍÍ¡¹¤Ê¤È¤³¤í¤Ë±þÍѤ¬¸«¤é¤ì¤ë¡¥Ìڤϡ¤¥é¥Ù¥ë¤È¸Æ¤Ð¤ì¤ë¥Ç¡¼¥¿¤ò³ÊǼ¤¹¤ë¤¿¤á¤Î ¥Î¡¼¥É(node)¤Î½¸¤Þ¤ê¤«¤é¹½À®¤µ¤ì¡¤³Æ¥Î¡¼¥É¤Ï¡¤ 0 ¸Ä°Ê¾å¤Î»Ò¥Î¡¼¥É(child node)¤ò»ý¤Ä¤è¤¦¤Ê³¬Áع½Â¤¤ò¤Ê¤·¤Æ¤¤¤ë¡¥ ³¬Áع½Â¤¤Î°ìÈÖ¡Ö¾å¡×¤Î¥Î¡¼¥É¤òº¬(root)¤È¸Æ¤Ö¡¥ ÌÚ¤ÏÍÍ¡¹¤Ê¤È¤³¤í¤Ë±þÍѤµ¤ì¤Æ¤¤¤Æ¡¤UNIX ¤Î¥Õ¥¡¥¤¥ë¥·¥¹¥Æ¥à¤ÏÌÚ¹½Â¤¤Î°ìÎã¤Ç¤¢¤ë¡¥ ÌÚ¹½Â¤¤Î¤¦¤Á³Æ¥Î¡¼¥É¤Î»Ò¶¡¤Î(ºÇÂç)¿ô n ¤¬·è¤Þ¤Ã¤Æ¤¤¤ë¤â¤Î¤ò nʬÌÚ¤È ¸Æ¤Ö¡¥n=1¤Î¤â¤Î¤Ï¥ê¥¹¥È¤ÈƱÍͤʹ½Â¤¤Ë¤Ê¤ë¡¥¤³¤³¤Ç¤ÏºÇ¤âñ½ã¤ÊÆóʬÌÚ¤ò °·¤Ã¤Æ¤¤¤¯¡¥

ÆóʬÌÚ¹½Â¤¤ÏºÆµ¢Åª¤Ë¼¡¤Î¤è¤¦¤ËÄêµÁ¤¹¤ë¤³¤È¤¬¤Ç¤­¤ë¡¥

¤³¤ì¤ò Objective Caml ¤Î·¿ÄêµÁ¤Ëľ¤·¤¿¤â¤Î¤¬°Ê²¼¤ÎÄêµÁ¤Ç¤¢¤ë¡¥

# type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;
type 'a tree = Lf | Br of 'a * 'a tree * 'a tree

Lf ¤ÏÍÕ¡¤Br (»Þ/branch)¤Ï¥Î¡¼¥É¤Î¤³¤È¤Ç¡¤º¸±¦¤ÎÉôʬÌÚ¤È ¤½¤Î¥é¥Ù¥ë¤«¤é tree ¤ò¹½À®¤¹¤ë¡¥ ¤Þ¤¿¡¤¥ê¥¹¥È¤ÈƱÍÍ¡¤¥Ç¡¼¥¿¹½Â¤¤òµ­½Ò¤¹¤ë¥Ç¡¼¥¿·¿¤Ç¤¢¤ë¤Î¤Ç¥é¥Ù¥ë¤Î·¿¤ÏÆÃÄê ¤·¤Æ¤¤¤Ê¤¤(¿ÁêŪ¤Ç¤¢¤ë)¡¥

¼ÂºÝ¤ÎÌÚ¤ÎÎã¤ò¸«¤Æ¤ß¤è¤¦¡¥Î㤨¤Ð¡¤

a −[dl] −[dr]b −[dl]c −[dl] −[dr]def

¤Î¤è¤¦¤Êʸ»ú¤«¤é¤Ê¤ëÌڤϡ¤

# let chartree = Br ('a', Br ('b', Br ('d', Lf, Lf), Lf),
                          Br ('c', Br ('e', Lf, Lf), Br ('f', Lf, Lf)));;
val chartree : char tree =
Br ('a', Br ('b', Br ('d', Lf, Lf), Lf),
Br ('c', Br ('e', Lf, Lf), Br ('f', Lf, Lf)))

¤Èɽ¸½¤Ç¤­¤ë¡¥»Ò¥Î¡¼¥É¤Î¤Ê¤¤¥Î¡¼¥É¤Ï Br (.., Lf, Lf) ¤Çɽ¤·¤Æ¤¤¤ë¡¥

ÌÚ¤ÎÂ礭¤µ¤ò·×¤ë»Øɸ¤È¤·¤Æ¤Ï¡¤(¥é¥Ù¥ë¤Ä¤­)¥Î¡¼¥É¤Î¿ô¤ä¡¤º¬¤«¤é°ìÈÖ¡Ö¿¼¤¤¡× ¥Î¡¼¥É¤Þ¤Ç¤Î¿¼¤µ¤òÍѤ¤¤ë¡¥°Ê²¼¤Î´Ø¿ô¤Ï¤½¤ì¤é¤òµá¤á¤ë¤â¤Î¤Ç¤¢¤ë¡¥

# let rec size = function
      Lf -> 0
    | Br (_, left, right) -> 1 + size left + size right;;
val size : 'a tree -> int = <fun>
# let rec depth = function
       Lf -> 0
     | Br (_, left, right) -> 1 + max (depth left) (depth right);;
val depth : 'a tree -> int = <fun>

ÌÀ¤é¤«¤Ë¡¤ÆóʬÌÚ t ¤ËÂФ·¤Æ¤Ï¾ï¤Ë¡¤size(t) ≤ 2depth(t) − 1 ¤¬ À®Î©¤¹¤ë¡¥¤Þ¤¿¡¤size(t) = 2depth(t) − 1 ¤Ç¤¢¤ë¤è¤¦¤ÊÆóʬÌÚ¤ò ´°Á´ÆóʬÌÚ(complete binary tree)¤È¸Æ¤Ö¡¥

# let comptree = Br(1, Br(2, Br(4, Lf, Lf),
                             Br(5, Lf, Lf)),
                       Br(3, Br(6, Lf, Lf),
                             Br(7, Lf, Lf)));;
val comptree : int tree =
Br (1, Br (2, Br (4, Lf, Lf), Br (5, Lf, Lf)),
Br (3, Br (6, Lf, Lf), Br (7, Lf, Lf)))

¤Ï¡¤¿¼¤µ3¤Î´°Á´ÆóʬÌÚ¤ÎÎã¤Ç¤¢¤ë¡¥

# size comptree;;
- : int = 7
# depth comptree;;
- : int = 3

¤µ¤Æ¡¤ÌÚ¹½Â¤¤«¤éÍ×ÁǤòÎóµó¤¹¤ëÊýË¡¤ò¹Í¤¨¤Æ¤ß¤è¤¦¡¥Îóµó¤¹¤ë¤¿¤á ¤Ë¤Ï¡¤¥é¥Ù¥ë¥Ç¡¼¥¿¤ËŬÅö¤Ê½ç½ø¤ò¤Ä¤±¤ëɬÍפ¬¤¢¤ë¡¥¤³¤Î½ç½ø¤ÎÉÕ¤±Êý¤ÎÂåɽŪ¤Ê ¤â¤Î£³¤Ä¡¤¹Ô¤­¤¬¤±½ç(preorder), Ä̤꤬¤±½ç(inorder)¡¤ µ¢¤ê¤¬¤±½ç(postorder)¤ò¾Ò²ð¤¹¤ë¡¥ Îóµó¤¹¤ë´Ø¿ô¤Ï¤¤¤º¤ì¤â¥ê¥¹¥È¤òÊÖ¤¹´Ø¿ô¤È¤·¤ÆÄêµÁ¤µ¤ì¤ë¤¬¡¤ÀâÌÀ¤È¤·¤Æ¤Ï ÌڤΥΡ¼¥É¤òˬ¤ì¤ë½çÈ֤ΤĤ±¤«¤¿¤È¤·¤ÆÀâÌÀ¤¹¤ë¡¥

¹Ô¤­¤¬¤±½ç¤Ï¡¤Ë¬¤ì¤¿¥é¥Ù¥ë¤ò¤Þ¤º¼è¤ê¾å¤²¤Æ¤«¤é¡¤º¸¤ÎÉôʬÌÚ¡¤±¦¤ÎÉôʬÌÚ ¤Î½ç¤Ç¥Î¡¼¥É¤òÎóµó¤¹¤ë¡¥

# let rec preorder = function
      Lf -> []
    | Br (x, left, right) -> x :: (preorder left) @ (preorder right);;
val preorder : 'a tree -> 'a list = <fun>
# preorder comptree;;
- : int list = [1; 2; 4; 5; 3; 6; 7]

Ä̤꤬¤±½ç¤Ï¡¤¤Þ¤ºº¸¤ÎÉôʬÌÚ¤«¤é»Ï¤á¤Æ¡¤±¦¤ÎÌڤ˹Ԥ¯Á°¤Ë¡¤¥é¥Ù¥ë¤ò ¼è¤ê¾å¤²¤ë¡¥

# let rec inorder = function
      Lf -> []
    | Br (x, left, right) -> (inorder left) @ (x :: inorder right);;
val inorder : 'a tree -> 'a list = <fun>
# inorder comptree;;
- : int list = [4; 2; 5; 1; 6; 3; 7]

µ¢¤ê¤¬¤±½ç¤Ï¡¤¤Þ¤º¡¤ÉôʬÌÚ¤òÎóµó¤·¤Æ¤«¤é¡¤ºÇ¸å¤Ë¥Î¡¼¥É¥é¥Ù¥ë¤ò¼è¤ê¾å¤²¤ë¡¥

# let rec postorder = function
      Lf -> []
    | Br (x, left, right) -> (postorder left) @ (postorder right) @ [x];;
val postorder : 'a tree -> 'a list = <fun>
# postorder comptree;;
- : int list = [4; 5; 2; 6; 7; 3; 1]

¤³¤ì¤é¤ÎÄêµÁ¤Ï¡¤@ ¤ò»È¤Ã¤Æ¤¤¤ë¤»¤¤¤Ç¡¤¥µ¥¤¥º¤ËÈæ¤Ù¤Æ¿¼¤µ¤¬Â礭¤¤¤è¤¦¤Ê (¥¢¥ó¥Ð¥é¥ó¥¹¤Ê)ÌÚ¤ËÂФ·¤Æ¸úΨ¤¬Îɤ¯¤Ê¤¤¡¥¤³¤ì¤ò²þÁ±¤·¤¿¤Î¤¬¼¡¤ÎÄêµÁ¤Ç¤¢¤ë¡¥ ÎóµóºÑÍ×ÁǤò°ú¿ô¤È¤·¤ÆÄɲä·¡¤³Æ¥Î¡¼¥É¤Ç¤Ï¤½¤Î¥ê¥¹¥È¤ËÍ×ÁǤòÄɲÃ(cons)¤¹¤ë ¤³¤È¤À¤±¤Ç¡¤·×»»¤ò¹Ô¤Ã¤Æ¤¤¤ë¡¥(¤³¤ÎÎत¤ÎÄêµÁ¤Ï¡¤¸úΨ¤òÎɤ¯¤¹¤ë¤¿¤á¤Ë¤ï¤ê¤È ¤è¤¯¤È¤é¤ì¤ë¼ê¤Ç¤¢¤ë¤Î¤Ç¡¤¾å¤ÎÁÇľ¤ÊÄêµÁ¤òÍý²ò¤·¤¿¤¦¤¨¤Ç¡¤¥Þ¥¹¥¿¡¼¤¹¤ë²ÁÃÍ ¤Ï¤¢¤ë¡¥)

# let rec preord t l = 
    match t with
      Lf -> l
    | Br(x, left, right) -> x :: (preord left (preord right l));;
val preord : 'a tree -> 'a list -> 'a list = <fun>
# preord comptree [];;
- : int list = [1; 2; 4; 5; 3; 6; 7]
Æóʬõº÷ÌÚ

Æóʬõº÷ÌÚ(binary search tree)¤Ï¡¤½ç½ø¤Î¤Ä¤±¤é¤ì¤ë ¥Ç¡¼¥¿¤ò³ÊǼ¤¹¤ë¤È¤­¤Ë¡¤¤¢¤È¤Ç¸¡º÷¤¬¤·¤ä¤¹¤¤¤è¤¦¤Ë¡¤°ìÄê¤Îµ¬Â§¤Ë ¤·¤¿¤¬¤Ã¤Æ¥Ç¡¼¥¿¤òÇÛÃÖ¤·¤¿ÌڤǤ¢¤ë¡¥¶ñÂÎŪ¤Ë¤Ï¡¤¤¢¤ë¥Î¡¼¥É¤Îº¸¤Î ÉôʬÌڤˤϤ½¤Î¥Î¡¼¥É¾å¤Î¥Ç¡¼¥¿¤è¤ê¾®¤µ¤¤¥Ç¡¼¥¿¤À¤±¤¬¡¤ ±¦¤ÎÉôʬÌڤˤÏÂ礭¤¤¥Ç¡¼¥¿¤À¤±¤¬Ê¤ó¤Ç¤¤¤ë¤è¤¦¤ÊÌڤǤ¢¤ë¡¥ Î㤨¤Ð

Br (4, Br (2, Lf, Br (3, Lf, Lf)), Br (5, Lf, Lf))

¤Îɽ¤¹ÌÚ¤ÏÆóʬõº÷ÌڤǤ¢¤ë¤¬¡¤

Br (3, Br (2, Br (4, Lf, Lf), Lf), Br (5, Lf, Lf))

¤Ï¤½¤¦¤Ç¤Ï¤Ê¤¤¡¥

Æóʬõº÷ÌÚ¾å¤Ç¡¤¤¢¤ëÍ×ÁǤ¬ÌÚ¤ÎÃæ¤Ë¤¢¤ë¤«¤òÌ䤤¹ç¤ï¤»¤ë mem¡¤ Í×ÁǤòÌÚ¤ËÄɲ乤ë add ´Ø¿ô¤Ï¤½¤ì¤¾¤ì°Ê²¼¤Î¤è¤¦¤Ë¤Ê¤ë¡¥

# let rec mem t x =
    match t with
      Lf -> false
    | Br (y, left, right) -> 
        if x = y then true 
        else if x < y then mem left x else mem right x
  let rec add t x =
    match t with
      Lf -> Br (x, Lf, Lf)
    | (Br (y, left, right) as whole) ->
        if x = y then whole
        else if x < y then Br(y, add left x, right) else Br(y, left, add right x);;
val mem : 'a tree -> 'a -> bool = <fun>
val add : 'a tree -> 'a -> 'a tree = <fun>

ÄêµÁ¤«¤é¤ï¤«¤ë¤è¤¦¤Ë¤É¤Á¤é¤â·×»»¤Î¹½Â¤¤ÏƱ¤¸¤Ç¡¤

Ʊ¤¸¥Ç¡¼¥¿¤Î½¸¹ç¤Ç¤â¡¤ÍÍ¡¹¤Ê·Á¤ÎÌÚ¤¬¹Í¤¨¤é¤ì¤ë¡¥ õº÷¤Î¸úΨ¤Ï¡¤Ìڤο¼¤µ¤Ë¤è¤ë¤Î¤Ç¡¤¿¼¤µ¤¬¤Ê¤ë¤Ù¤¯Àõ¤¤ÌÚ¤ò°Ý»ý ¤¹¤ë¤Î¤¬Æóʬõº÷ÌÚ¤ò°·¤¦ºÝ¤ÎÌÜɸ¤Î¤Ò¤È¤Ä¤È¤Ê¤ë¡¥

6.5  Case Study: ̵¸Â¥ê¥¹¥È

¤â¤¦¤Ò¤È¤Ä¡¤±þÍÑÎã¤È¤·¤Æ¡¤Ìµ¸Â¤Î¥Ç¡¼¥¿Îó¤òɽ¤¹ ¥Ç¡¼¥¿·¿¤ò¤ß¤Æ¤ß¤è¤¦¡¥Ìµ¸ÂÎó¤òÍ­¸Â¤Î¥á¥â¥ê¾å¤Ë¤½¤Î¤Þ¤Þɽ¸½¤¹¤ë¤³¤È¤Ï¤Ç¤­¤Ê ¤¤¤Î¤Ç¡¤¹©Éפ¬É¬ÍפǤ¢¤ë¡¥¤³¤³¤Ç¤Ï̵¸ÂÎó¤Ï¡¤ÀèƬÍ×ÁǤȡ¤¡Ö°Ê¹ß¤Î(̵¸Â)Îó¤ò ·×»»¤¹¤ë¤¿¤á¤Î´Ø¿ô¡×¤ÎÁȤÇɽ¸½¤¹¤ë¡¥¤³¤Î¡Ö´Ø¿ô¡×¤ÏÆä˰ú¿ô¤È¤Ê¤ë¤Ù¤­ ¾ðÊó¤òɬÍפȤ·¤Ê¤¤¤Î¤Ç¡¤unit ¤«¤é¤Î´Ø¿ô¤È¤·¤Æɽ¸½¤·¤è¤¦¡¥ ¤³¤ì¤ò½ñ¤¤¤¿¤Î¤¬°Ê²¼¤Î type Àë¸À¤Ç¤¢¤ë¡¥

# type 'a seq = Cons of 'a * (unit -> 'a seq);;
type 'a seq = Cons of 'a * (unit -> 'a seq)

seq ¤Ï list ¤ä tree ¤Î¤è¤¦¤ËÍ×ÁÇ·¿¤Ë´Ø¤·¤Æ¿ÁêŪ¤Ç¤¢¤ë¡¥ Cons ¤ÏÍ×ÁǤòÀèƬ¤ËÄɲ乤뤿¤á¤Î¥³¥ó¥¹¥È¥é¥¯¥¿¤Ç¤¢¤ê¡¤ of °Ê²¼¤Î·¿¤¬¼¨¤¹¤è¤¦¤Ë¡¤tail Éôʬ¤Ï´Ø¿ô·¿¤Ë¤Ê¤Ã¤Æ¤¤¤ë¡¥¤³¤Î¥ô¥¡¥ê¥¢¥ó¥È·¿ ¤Ï¥³¥ó¥¹¥È¥é¥¯¥¿¤¬°ì¤Ä¤·¤«¤Ê¤¤¤¿¤á¡¤¥ô¥¡¥ê¥¢¥ó¥È·¿¤ò¤ï¤¶¤ï¤¶»È¤ï¤º¤Ë¡¤Í×ÁǤȴؿô¤ÎÁȤÇɽ¸½¤¹¤ë¤³¤È¤â¸¶ÍýŪ¤Ë²Äǽ¤Ç¤¢¤ë¡¥¤³¤Î¤è¤¦¤Ê·¿¤òÀë¸À¤¹¤ë¤Î ¤Ï¡¤¥Ç¡¼¥¿Ãê¾Ý¤Î¼êÃʤΤҤȤĤǤ¢¤ë¤È¹Í¤¨¤é¤ì¤ë¡¥¤Ä¤Þ¤ê¡¤¥×¥í¥°¥é¥Þ¤¬ ¥Ç¡¼¥¿¤Ë¤³¤á¤¿°ÕÌ£¤ò¥×¥í¥°¥é¥à¾å¤ÇÆɤ߼è¤ë¤³¤È¤¬¤Ç¤­¡¤¤¿¤Þ¤¿¤ÞƱ¤¸É½¸½ ¤ò¤â¤Ä°ã¤¦°ÕÌ£¤Î¥Ç¡¼¥¿¤Èº®Í𤹤ë²ÄǽÀ­¤¬¾¯¤Ê¤¯¤Ê¤ë¡¤¤È¤¤¤¦°ÕµÁ¤¬¤¢¤ë¡¥

¼¡¤Î´Ø¿ô from ¤Ï¡¤À°¿ô n ¤«¤é1¤º¤ÄÁý¤¨¤ë̵¸ÂÎó¤òÀ¸À®¤¹¤ë¡¥

# let rec from n = Cons (n, fun () -> from (n + 1));;
val from : int -> int seq = <fun>

fun () -> ¤ËÃíÌܤ·¤¿¤¤¡¥Ìµ¸ÂÎó¤Ï¡¤fun () -> ... »È¤Ã¤Æ ´Ø¿ô¤ò¹½À®¤·¡¤tail Éô¤Îɾ²Á¤ò¡¤É¬ÍפʤȤ­¤Þ¤ÇÃ٤餻¤Æ¤¤¤ë¤«¤é ¼Â¸½¤Ç¤­¤Æ¤¤¤ë¤Î¤Ç¤¢¤ë¡¥Æ±Íͤʴؿô¤ò¥ê¥¹¥È¤ò»È¤Ã¤ÆÄê µÁ¤·¤Æ¤â¡¤

let rec list_from n = n :: list_from (n + 1)

¤Ò¤È¤¿¤Ó¸Æ¤Ó½Ð¤µ¤ì¤ë¤È¡¤list_from ¤Î¸Æ¤Ó½Ð¤·¤ò̵¸Â¤Ë¹Ô¤Ã¤Æ¤·¤Þ¤¦¤Î¤Ç ¤¦¤Þ¤¯¤¤¤«¤Ê¤¤¡¥

from ¤ÎÄêµÁ¤Ë¤ß¤é¤ì¤ë¤è¤¦¤Ë¡¤¼°¤Îɾ²Á¤òÃ٤餻¤ë¤¿¤á¤Ë ƳÆþ¤µ¤ì¤ë´Ø¿ô¤ò¥µ¥ó¥¯(thunk)¤È¸Æ¤Ö¡¥ ;Ã̤Ǥ¢¤ë¤¬¡¤¥µ¥ó¥¯¤ÎÌÀ¼¨Åª¤ÊƳÆþ¤ÏÃÙ±äɾ²Áµ¡¹½¤ò»ý¤Ä¸À¸ì¤Ç¤¢¤ì¤ÐɬÍפΤʤ¤¤È¤³¤í¤Ç¤¢¤ë(¤â¤È¤â¤ÈÉôʬ¼°¤Îɾ²Á¤Ï ɬÍפˤʤë¤Þ¤ÇÃ٤餵¤ì¤ë)¤¿¤á¡¤¤³¤Î¤è¤¦¤Ê̵¸Â¤Î¹½Â¤¤Ï lazy ¤Ê¸À¸ì¤ÎÆÀ °Õ¤È¤¹¤ë¤È¤³¤í¤Ç¤¢¤ë¡¥

Î󤫤éÀèƬÍ×ÁÇ¡¤¸å³¤ÎÎó¤òÊÖ¤¹´Ø¿ô¡¤ÀèƬ¤«¤é n Í×ÁǤò¥ê¥¹¥È¤È¤·¤Æ¼è½Ð¤¹ ´Ø¿ô¤Ï¡¤

# let head (Cons (x, _)) = x;;
val head : 'a seq -> 'a = <fun>
# let tail (Cons (_, f)) = f ();;
val tail : 'a seq -> 'a seq = <fun>
# let rec take n s = 
    if n = 0 then [] else head s :: take (n - 1) (tail s);;
val take : int -> 'a seq -> 'a list = <fun>
# take 10 (from 4);;
- : int list = [4; 5; 6; 7; 8; 9; 10; 11; 12; 13]

¤ÈÄêµÁ¤µ¤ì¤ë¡¥tail ´Ø¿ô¤ÎËÜÂΤǤϥµ¥ó¥¯¤Ë () ¤òŬÍѤ·¤Æ¡¤¸å³Îó¤ò ·×»»¤·¤Æ¤¤¤ë¡¥ ¥³¥ó¥¹¥È¥é¥¯¥¿¤¬¤Ò¤È¤Ä¤Î¥ô¥¡¥ê¥¢¥ó¥È·¿¤ËÂФ·¤Æ¤Ï¡¤¾ì¹ç ¤ï¤±¤ò¤¹¤ëɬÍפ¬¤Ê¤¤ ¤Î¤Ç¡¤match ¤ò»È¤ï¤º¤Ë°ú¿ô¤Ë¥Ñ¥¿¡¼¥ó¤òľÀܽñ¤¤ ¤Æ¤â»Ù¾ã¤¬¤Ê¤¤¡¥ take ¤Ï¥ê¥¹¥È¤ËÂФ·¤Æ¤Î¤â¤Î¤ÈƱÍͤËÄêµÁ¤Ç¤­¤ë¡¥

¤µ¤Æ¡¤Ìµ¸ÂÎó¤ËÂФ¹¤ë map ¤òÄêµÁ¤·¤Æ¤ß¤è¤¦¡¥

# let rec mapseq f (Cons (x, tail)) =
    Cons (f x, fun () -> mapseq f (tail ()));;
val mapseq : ('a -> 'b) -> 'a seq -> 'b seq = <fun>
# let reciprocals = mapseq (fun x -> 1.0 /. float_of_int x) (from 2);;
val reciprocals : float seq = Cons (0.5, <fun>)
# take 5 reciprocals;;
- : float list = [0.5; 0.333333333333333315; 0.25; 0.2; 0.166666666666666657]

ÃíÌܤ¹¤Ù¤­ÅÀ¤Ï¡¤reciprocals ¤ÎÃͤò¸«¤ë¤È¤ï¤«¤ë¤è¤¦¤Ë¡¤ 0.5 °Ê¹ß¤ÎÍ×ÁÇ¤Ï take ¤ò¤¹¤ë¤Þ¤Ç¼ÂºÝ¤Ë¤Ï·×»»¤µ¤ì¤Æ¤¤¤Ê¤¤¤³¤È¤Ç¤¢¤ë¡¥ take ¤ÎÃæ¤Ç¡¤tail ¤ò¸Æ¤Ó½Ð¤¹Å٤˵տô¤¬·×»»¤µ¤ì¤Æ¤¤¤¯¡¥

;Ã̤Ǥ¢¤ë¤¬¡¤Ê£»¨¤Ê¥Ç¡¼¥¿·¿¤Ë¤¿¤¤¤¹¤ë´Ø¿ô¤ò½ñ¤¤¤Æ¤¤¤ì¤Ð¤¤¤ë¤Û¤É·¿¾ðÊó ¤¬¥Ç¥Ð¥°¤ËÌòΩ¤Ä¤³¤È¤¬¼Â´¶¤Ç¤­¤ë¡¥¾å¤Î´Ø¿ôÄêµÁ¤Ç¡¤¤Ä¤¤¡¤¥µ¥ó¥¯Æ³Æþ¤Î¤¿ ¤á¤Î fun () -> ¤ò½ñ¤­Ëº¤ì¤Æ¤·¤Þ¤Ã¤¿¤ê¡¤¥µ¥ó¥¯¤Îɾ²Á(tail ())¤ò¤·Ëº ¤ì¤¿¤ê¤¹¤ë¤Î¤À¤¬¡¤·¿¤Î¤ª¤«¤²¤Ç(¥¨¥é¡¼¥á¥Ã¥»¡¼¥¸¤Ë¤Ê¤ì¤ì¤Ð)¤¹¤°¤Ë´Ö°ã¤¤ ¤òȯ¸«¤¹¤ë¤³¤È¤¬¤Ç¤­¤ë¡¥

¥¨¥é¥È¥¹¥Æ¥Í¥¹¤Î¤Õ¤ë¤¤

¤µ¤Æ¡¤¤â¤¦¤¹¤³¤·ÌÌÇò¤¤Ìµ¸ÂÎó¤Î±þÍÑÎã¤ò¤ß¤Æ¤ß¤¿¤¤¡¥ ¥¨¥é¥È¥¹¥Æ¥Í¥¹¤Î¤Õ¤ë¤¤¤ÏÁÇ¿ô¤òµá¤á¤ë¤¿¤á¤Î·×»»ÊýË¡¤Ç¡¤ 2°Ê¾å¤ÎÀ°¿ô¤ÎÎ󤫤顤

¤È¤·¤ÆÁÇ¿ô¤ÎÎó¤òµá¤á¤ëÊýË¡¤Ç¤¢¤ë¡¥ ¤³¤³¤Ç¤Ï¡¤seq ·¿¤òÍѤ¤¤Æ¥¨¥é¥È¥¹¥Æ¥Í¥¹¤Î¤Õ¤ë¤¤¤ò¼Â¸½¤·¤Æ¤ß¤è¤¦¡¥ ¤Þ¤ºÉ¬ÍפʤΤϡ¤À°¿ôÎ󤫤é n ¤ÎÇÜ¿ô¤ò¼è¤êµî¤Ã¤¿Îó¤ò ÊÖ¤¹´Ø¿ô sift ¤Ç¤¢¤ë¡¥

let rec sift n ... = ...;;

¤³¤ì¤ò»È¤¦¤È¥¨¥é¥È¥¹¥Æ¥Í¥¹¤Î¤Õ¤ë¤¤¤Ï¡¤¼¡¤Î¤è¤¦¤ËÄêµÁ¤Ç¤­¤ë¡¥

# let rec sieve (Cons (x, f)) = Cons (x, fun () -> sieve (sift x (f())));;
val sieve : int seq -> int seq = <fun>
# let primes = sieve (from 2);;
val primes : int seq = Cons (2, <fun>)
# take 20 primes;;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71]
# let rec nthseq n (Cons (x, f)) =
    if n = 1 then x else nthseq (n - 1) (f());;
val nthseq : int -> 'a seq -> 'a = <fun>
# nthseq 1000 primes;;
- : int = 7919

6.6  Îý½¬ÌäÂê

Exercise 1  °Ê²¼¤Î¥ì¥³¡¼¥É·¿ loc_fig ¤Ï¡¤¿Þ·Á¤ËxyÊ¿Ì̾å¤Ç¤Î°ÌÃÖ¾ðÊó¤ò¤â¤¿¤»¤¿¤â¤Î¤Ç ¤¢¤ë¡¥ÀµÊý·Á¡¤Ä¹Êý·Á¤Ï¡¤³ÆÊÕ¤¬¼´¤ËʹԤǤ¢¤ë¤è¤¦¤ËÇÛÃÖ¤µ¤ì¤Æ¤¤¤ë¤È²¾Äê(ĹÊý ·Á¤Ë´Ø¤·¤Æ¤Ï¡¤Rectangle (x, y) ¤Î x ¤Îɽ¤¹ÊÕ¤¬x¼´¤Ëʹԡ¤¤È¤¹¤ë¡¥)¤·¡¤ Æó¤Ä¤Î¿Þ·Á¤¬½Å¤Ê¤ê¤ò»ý¤Ä¤«È½Äꤹ¤ë´Ø¿ô overlap ¤òÄêµÁ¤»¤è¡¥
type loc_fig = {x : int; y : int; fig : figure};;
Exercise 2  nat ·¿¤ÎÃͤò¤½¤ì¤¬É½¸½¤¹¤ë int ¤ËÊÑ´¹¤¹¤ë´Ø¿ô int_of_nat, nat ¾å¤Î³Ý¤±»»¤ò¹Ô¤¦´Ø¿ô mul¡¤nat ¾å¤Î°ú¤­»»¤ò¹Ô¤¦ ´Ø¿ô(¤¿¤À¤· 0 − n = 0) monus (¥â¡¼¥Ê¥¹) ¤òÄêµÁ¤»¤è¡¥ (mul, monus ¤Ï *, - ¤Ê¤É¤Î½õ¤±¤ò¼Ú¤ê¤º¡¤ nat ·¿¤ÎÃͤ«¤é¡ÖľÀܡ׷׻»¤¹¤ë¤è¤¦¤Ë¤»¤è¡¥)
Exercise 3  ¾å¤Î monus ´Ø¿ô¤òÊѹ¹¤·¤Æ¡¤0 − n (n > 0) ¤Ï None ¤òÊÖ¤¹ nat -> nat -> nat option ·¿¤Î´Ø¿ô minus ¤òÄêµÁ¤»¤è¡¥
Exercise 4  ¿¼¤µ n ¤ÇÁ´¤Æ¤Î¥Î¡¼¥É¤Î¥é¥Ù¥ë¤¬ x ¤Ç¤¢¤ë¤è¤¦¤Ê ´°Á´ÆóʬÌÚ¤òÀ¸À®¤¹¤ë´Ø¿ôcomptree x n ¤òÄêµÁ¤»¤è¡¥
Exercise 5  preord ¤ÈƱÍͤÊÊýË¡¤Ç¡¤Ä̤꤬¤±½ç¡¤µ¢¤ê¤¬¤±½ç¤ËÎóµó¤¹¤ë´Ø¿ô inord, postord ¤òÄêµÁ¤»¤è¡¥
Exercise 6  ÆóʬÌڤκ¸±¦¤òȿž¤µ¤»¤¿ÌÚ¤òÊÖ¤¹´Ø¿ô reflect ¤òÄêµÁ¤»¤è¡¥
# reflect comptree;;
- : int tree =
Br (1, Br (3, Br (7, Lf, Lf), Br (6, Lf, Lf)),
Br (2, Br (5, Lf, Lf), Br (4, Lf, Lf)))
¤Þ¤¿¡¤Ç¤°Õ¤ÎÆóʬÌÚ t ¤ËÂФ·¤ÆÀ®Î©¤¹¤ë¡¤°Ê²¼¤ÎÊýÄø¼°¤ò´°À®¤µ¤»¤è¡¥
  preorder(reflect(t))=
  inorder(reflect(t))=
  postorder(reflect(t))=?
Exercise 7  °Ê²¼¤Ï¡¤Â­¤·»»¤È³Ý¤±»»¤«¤é¤Ê¤ë¿ô¼°¤Î¹½Ê¸¤òɽ¤·¤¿·¿ÄêµÁ¤Ç¤¢¤ë¡¥
# type arith = 
    Const of int | Add of arith * arith | Mul of arith * arith;;
type arith = Const of int | Add of arith * arith | Mul of arith * arith
# (* exp stands for (3+4) * (2+5) *)
  let exp = Mul (Add (Const 3, Const 4), Add (Const 2, Const 5));;
val exp : arith = Mul (Add (Const 3, Const 4), Add (Const 2, Const 5))
¿ô¼°¤Îʸ»úÎóɽ¸½¤òµá¤á¤ë´Ø¿ô string_of_arith, ʬÇÛ§¤òÍѤ¤¤Æ ¿ô¼°¤ò (i11 × ⋯ × i1n1) + ⋯ + (im1 × ⋯ × imnm) ¤Î·Á¤ËÊÑ·Á¤¹¤ë´Ø¿ô expand ¤òÄêµÁ¤»¤è¡¥
# string_of_arith exp;;
- : string = "((3+4)*(2+5))"
# string_of_arith (expand exp);;
- : string = "(((3*2)+(3*5))+((4*2)+(4*5)))"
(¥ª¥×¥·¥ç¥ó¤È¤·¤Æ) string_of_arith ¤Î½ÐÎÏ·ë²Ì¤Î³ç¸Ì¤ò¸º¤é¤¹¤è¤¦¤Ë¹©Éפ»¤è¡¥ (¾å¤Î½ÐÎÏÎã¤Ç¤Ï²¿¤â¹©Éפ·¤Æ¤¤¤Ê¤¤¡¥)
Exercise 8  1, 2, 3, 4 ¤«¤é¤Ê¤ë²Äǽ¤ÊÆóʬõº÷ÌڤηÁ¤òÎóµó¤·¡¤¤½¤ì¤¾¤ì¤Î·Á¤òºî¤ë¤¿¤á¤Ë¤Ï ¶õ¤ÎÌÚ¤«¤é»Ï¤á¤Æ¡¤¤É¤Î½çÈÖ¤ÇÍ×ÁǤò add ¤·¤Æ¤¤¤±¤Ð¤è¤¤¤«¼¨¤»¡¥
Exercise 9   ´Ø¿ô sift ¤òÄêµÁ¤·¡¤⟨ ¼«Ê¬¤Î³ØÀÒÈÖ¹æ+3000 ⟩ÈÖÌܤÎÁÇ¿ô¤òµá¤á¤è¡¥
Exercise 10  °Ê²¼¤ÇÄêµÁ¤µ¤ì¤ë ('a, 'b) sum ·¿¤Ï¡¤¡Öα·¿¤ÎÃͤ⤷¤¯¤Ï β·¿¤ÎÃ͡פȤ¤¤¦Ï½¸¹çŪ¤Ê¥Ç¡¼¥¿¤Î¹½À®¤ò¼¨¤¹·¿¤Ç¤¢¤ë¡¥
# type ('a, 'b) sum = Left of 'a | Right of 'b;;
type ('a, 'b) sum = Left of 'a | Right of 'b
# let float_of_int_or_float = function
      Left i -> float_of_int i
    | Right f -> f;;
val float_of_int_or_float : (int, float) sum -> float = <fun>
# float_of_int_or_float (Right 3.14);;
- : float = 3.14
# float_of_int_or_float (Left 2);;
- : float = 2.
¤³¤ì¤òƧ¤Þ¤¨¤Æ¡¤¼¡¤Î·¿¤ò¤â¤Ä´Ø¿ô¤òÄêµÁ¤»¤è¡¥
  1. 'a * ('b, 'c) sum -> ('a * 'b, 'a * 'c) sum
  2. ('a, 'b) sum * ('c, 'd) sum -> (('a * 'c, 'b * 'd) sum, ('a * 'd, 'b * 'c) sum) sum
  3. ('a -> 'b) * ('c -> 'b) -> ('a, 'c) sum -> 'b
  4. (('a, 'b) sum -> 'c) -> ('a -> 'c) * ('b -> 'c)
  5. ('a -> 'b, 'a -> 'c) sum -> ('a -> ('b,'c) sum)

1
ºÇ¸å¤Î ⟨ ·¿n ⟩ ¤ä ⟨ ¼°n ⟩ ¤Î¸å¤Ë ; ¤ò ¤Ä¤±¤Æ¤â¤è¤¤¡¥

Previous Up Next