Concurrent Clean 1部3章つづき

言語

正格に

関数foldrとは対照的に、要素は、foldlによって、リストと比較してちょうど逆順にグループ化される。関数foldlの定義はこのように書くことができる。

foldl :: (a->(b->a)) !a ![b] -> a
foldl op e []     = e
foldl op e [x:xs] = foldl op (op e x) xs

　要素eは、適切なアキュムレータとして資する為に正格にされている。

「正格に」は先に評価されるということ？

クラス

この事実は以下のソート関数の型によって表現される。

sort :: [a] -> [a] | Ord a

　これは以下のことを意味する。つまり、sortは、クラスOrdのインスタンスが定義されている型aのリストに作用する。このことは、もしある型、つまり、Tのオブジェクトにsortを適用したいならば、Tの多重定義演算子'<'のインスタンスもどこかで定義しなければならないと言うことを意味する。これで十分である。というのも、Ordの他のメンバ（<=、>等々）は'<'から導出できるからである。

sort関数の型にクラスOrd aが条件に入る。Ordはaに(<)が定義してあること。1章(1.5.5)では中で使う多重定義関数を列挙していた代わりのようなもの（ sort :: [a] -> [a] | < a ）。


ラベリング

照合しているパターンには、以下の定義の中でのように、特別シンボル"=:"を使用して、全体としてある名前を与えることもできる。

merge :: [a] [a] -> [a] | Ord a
merge []        ys     = ys
merge xs        []     = xs
merge p=:[x:xs] q=:[y:ys]
    | x <= y      = [x : merge xs q]
    | otherwise   = [y : merge p ys]

パターンマッチでは=:の右辺を使うけど、全体を左辺の名前で参照できる。

マージソートはこのmergeを使って

msort :: [a] -> [a] | Ord a
msort xs
    | len <= 1  = xs
    | otherwise = merge (msort ys) (msort zs)
where
    ys   = take half xs
    zs   = drop half xs
    half = len / 2
    len  = length xs

リスト内包表記

List Comprehension

集合の内包表記に類似して、結果リストの要素を計算するのに使用される値に、追加的な述語を加えることが出来る。その制約は垂直棒記号によってジェネレータから分離される。偶数である1から10の全ての整数の平方のリストは、以下のプログラムで計算される。

Start :: [Int]
Start = [x*x \\ x <- [1..10] | x mod 2 == 0]

Pythonだと[x * x for x in range(1, 11) if x % 2 == 0]になる。
このなかで'<-'と'|'はリスト内包表記の記号

二重バックスラッシュの後のリストの内包表記では、1つ以上のジェネレータが1つの','により分離されて現れることができる。これは、ジェネレータの入れ子組合せと呼ばれる。ジェネレータの入れ子組合せによって、二重バックスラッシュの前の式は、対応する束縛変数の全ての可能な組合せに対して計算される。例えば、

Start :: [(Int,Int)]
Start = [(x,y) \\ x<-[1..2], y<-[4..6]]

Pythonだと[(x, y) for x in range(1, 3) for y in range(4,7)]

さらに

ジェネレータを組み合わせるもう1つの方法は、','シンボルの代わりに'&'シンボルによってジェネレータを分離することで指示するジェネレータの並列組合せである。ジェネレータの並列組合せにより、i番目の要素が同時にいくつかのリストから引き出される。例えば、

Start ::　[(Int,Int)]
Start = [(x,y) \\ x<-[1..2] & y<-[4..6]]

　は、以下のリストに評価される。

[(1,4),(2,5)]

　最小のリストが枯渇すると、&演算子で組み合わされていた全てのジェネレータは停止する。

Pythonにはこの書き方はないかな？

内部的にはmapやfilterに変換されるらしい。

qsort :: [a] -> [a] | Ord a
qsort []     = []
qsort [a:xs] = qsort [x \\ x<-xs | x<a] ++ [a] ++ qsort [x \\ x<-xs | x>=a]

Pythonだと複雑化するかも。

def qsort(s):
  if len(s) == 0:
    return s
  else:
    a = s[0]
    xs = s[1:]
    return qsort([x for x in xs if x < a]) + [a] + qsort([x for x in xs if x >= a])

無限リスト

遅延型の一番の長所か。


組

CleanではTupleはリストと違って、いろいろな型の要素を持てるという役割がある（各要素に型を設定する）。個別に型を設定するので、要素数は固定。

pythonではいまいち存在意義が分からなかったzip関数もtupleとlistを区別する。

zip :: [a] [b] -> [(a,b)]
zip []     ys     = []
zip xs     []     = []
zip [x:xs] [y:ys] = [(x,y) : zip xs ys]

レコード

レコード型定義

まず型定義でそれの型を宣言しなければならない。例えば、

:: Person = { name       :: String
            , birthdate  :: (Int,Int,Int)
            , cleanuser  :: Bool
            }

データ(順序は任意、全メンバー必須)

SomePerson :: Person
SomePerson = { name      = "Rinus"
             , birthdate = (10,26,1952)
             , cleanuser = True
             }

多相レコード型

:: Pair a b = { first  :: a
              , second :: b
              }

パターンマッチ

fstR :: (Pair a b) -> a
fstR {first} = first

パターンマッチ２

IsCleanUser :: Person -> String
IsCleanUser {cleanuser = True} = "Yes"
IsCleanUser _                  = "No"

メンバー参照

GetPersonName :: Person -> String
GetPersonName person = person.name

メンバーを入れ替えたコピー

ChangePersonName :: Person String -> Person
ChangePersonName person newname = {person & name = newname}

レコード型は型名を明示して使う。型名重視？

AnotherPerson :: Person
AnotherPerson = { Person
                | name        = "Pieter"
                , birthdate   = (7,3,1957)
                , cleanuser   = True
                }
:: Point = { x :: Real
           , y :: Real
           }
MovePoint :: Point (Real,Real) -> Point
MovePoint p (dx,dy) = {p & x = p.x + dx, y = p.y + dy}

この例では、Pointのメンバーを増やしても、MovePointに変更はいらない（Pointのかわりにタプルを使うと変更が必要になるが）。

配列

Cleanでの配列は、同一型メンバー、個定要素数のデータ型。
メンバーアクセス

x = {1,2,3,4,5}
x.[5]

リストの場合

x = [1,2,3,4,5]
x!!5

リストはイテレータアクセスだが、配列はダイレクトアクセス（ランダムアクセス）になる違いがあるようだ。

配列も内包表記がある。

NewArray = {elem \\ elem <- ListA}
NewList = [elem \\ elem <-: ArrayA]

(日本語訳に誤植あり)配列の場合、<-:を使う。

{Int}は遅延配列。{!Int}は正格配列。正格配列のほうは計算済みということか。

基本型に対しては、{#Int}というように非ボックス配列にできる。これは参照配列ではなく、データが詰まった配列になる。文字列は{#Char}

"abc"

更新

Array5 :: *{Int}
Array5 = {1,3,5,7,9}
{Array5 & [0]=1,[1]=3,[2]=5,[3]=7,[4]=9}
{Array5 & [i]=2*i+1 \\ i <- [0..4]}
{Array5 & [i]=elem \\ elem <- [1,3..9] & <- [0..4]}

(ここも日本語訳は不足している)。更新するには一意的な配列（*{a}）であり、更新は破壊的らしい。

パターン

CopyElem  :: Int Int *{#a} -> {#a} | ArrayElem a
CopyElem i j a=:{[i]=ai} = {a & [j] = ai}

i番目のデータをj番目にコピー。

CopyElem2 :: Int Int *{#a} -> {#a} | ArrayElem a
CopyElem2 i j a = {a & [j] = a.[i]}

このCopyElem2はコンパイルエラー。aに「一意性」が消えるから？らしい。よくわからない。

4.3.4に一意型についての記述がある。一意とは、評価のどの時点でも参照カウントが１であること、とのこと。つまり、CopyElem2では、a & [j] = a.[i]より下の文法木でaの参照カウントが2（以上）になるため、一意ではなくなりエラーになる。パターンで変数にしていればOKらしい。



長い。3.7以降は明日か夜かかな。