top
recent
FP:inRuby
関連ページ
Ruby
FP
目次
- なんとなく...
- 途中経過...
- 遅延評価による無限リスト...
- リストのグループ化...
- 先達の技を学ぶ...
なんとなく
書き始めてしまった。
関数プログラミング
(本棚) の中で定義されている関数を Ruby で書き下ろしてみる、という感じ。合言葉は ``再・発・明！''
語彙は Miranda 準拠、ということになるんだろうか。
「巻末付録Ｂ 標準的な関数」を元に移植していくことにします。
…と思ったけどしょっぱなからくじけたので、好きな部分からつまみ喰いで。
----
関連ページ
FP
「Rubyで関数プログラミング」へのコメント
[[id:956]] 2002-08-08 22:54:56
途中経過
- group を追加
----
# $Id: FP.rb,v 1.10 2002/08/23 13:05:30 cake Exp cake $
module FP
def car(l)
lst = l.to_a
lst == [] ? nil : lst[0]
end
module_function :car
def cdr(l)
lst = l.to_a
lst == [] ? nil : lst[1..-1]
end
module_function :cdr
def cons(a, b)
[a] + b.to_a
end
module_function :cons
def map(f, xs)
xs.to_a.map {|x| f[x] }
end
module_function :map
def zip(xs, ys)
if xs.to_a == []
[]
elsif ys.to_a == []
[]
else
[[car(xs), car(ys)]] + zip(cdr(xs),cdr(ys))
end
end
module_function :zip
def zipwith(f, xs, ys)
zip(xs, ys).map {|a|
f[a[0], a[1]]
}
end
module_function :zipwith
def filter(f, xs)
xs.to_a.select {|x| f[x]}
end
module_function :filter
def foldr(f, x, l)
l.to_a == [] ? x : f[ car(l), foldr(f,x,cdr(l)) ]
end
module_function :foldr
def foldr1(f, l)
raise "Empty List" if l == []
l.to_a.size == 1 ? car(l) : f[ car(l), foldr1(f,cdr(l)) ]
end
module_function :foldr1
def foldl(f, x, l)
l.to_a == [] ? x : foldl(f, f[x, car(l)], cdr(l))
end
module_function :foldl
def foldl1(f, l)
raise "Empty List" if l == []
l.to_a.size == 1 ? car(l) : foldl(f, car(l), cdr(l))
end
module_function :foldl1
def scan_(f, x, l)
if l.to_a == [] then []
else scan(f, f[x, car(l)], cdr(l))
end
end
module_function :scan_
def scan(f, x, l)
cons x, scan_(f, x, l)
end
module_function :scan
def take(n, l)
if n < 1
[]
else
cons car(l), take(n-1, cdr(l))
end
end
module_function :take
def drop(n, l)
if n < 1
l
else
drop(n-1, cdr(l))
end
end
module_function :drop
def takewhile(p, l)
if l.to_a == []
[]
elsif p[ car(l) ]
cons car(l), takewhile(p, cdr(l))
else
[]
end
end
module_function :takewhile
def dropwhile(p, l)
if l.to_a == []
[]
elsif p[ car(l) ]
dropwhile(p, cdr(l))
else
l.to_a
end
end
module_function :dropwhile
def copy(x, n)
if n < 1 then
[]
else
[x] + copy(x, n-1)
end
end
module_function :copy
def group(n, l)
if l.to_a.size <= n then [l]
else
cons(take(n, l), group(n, drop(n, l)))
end
end
module_function :group
end
#from SICP-3.5 "Streams"
module FPstream
def delay(&expr)
expr
end
module_function :delay
def force(promise)
if promise.is_a? Proc
promise.call
else
promise
end
end
module_function :force
def cons(a, &b)
[a, b]
end
module_function :cons
def car(stream)
FP.car(stream)
end
module_function :car
def cdr(stream)
force(FP.car(FP.cdr(stream)))
end
module_function :cdr
def ref(s, n)
if n == 0
car(s)
else
ref(cdr(s), n - 1)
end
end
module_function :ref
def map(proc, s)
if s == []
[]
else
cons(proc[car(s)]) { map(proc, cdr(s)) }
end
end
module_function :map
def interval(from, to)
if from > to
[]
else
cons(from) { interval(from + 1, to) }
end
end
module_function :interval
def filter(pred, s)
if s == []
[]
elsif pred[car(s)]
cons(car(s)) { filter(pred, cdr(s)) }
else
filter(pred, cdr(s))
end
end
module_function :filter
end
if __FILE__ == "FP.rb"
p "zip 1..4, 10..14"
p FP.zip 1..4, 10..14
p "zipwith x + y"
p FP.zipwith(lambda{|x,y| "#{x} + #{y}" }, 1..3, 11..13)
p "filter evens"
p FP.filter(lambda{|x| x % 2 == 0}, 1..10)
p "FP.take(3, 1..5)"
p FP.take(3, 1..5)
p "FP.drop(3, 1..5)"
p FP.drop(3, 1..5)
p "FP.takewhile(proc{|x| x < 3}, 1..5)"
p FP.takewhile(proc{|x| x < 3}, 1..5)
p "FP.dropwhile(proc{|x| x < 3}, 1..5)"
p FP.dropwhile(proc{|x| x < 3}, 1..5)
p "foldr"
p FP.foldr(lambda{|x,y| FP.cons(x,y)}, 0, 1..6)
p "foldr1"
p FP.foldr1(lambda{|x,y| FP.cons(x,y)}, 1..6)
p "foldl"
p FP.foldl(lambda{|x,y| FP.cons(x,y)}, 0, 1..6)
p "foldl1"
p FP.foldl1(lambda{|x,y| FP.cons(x,y)}, 1..6)
p 'copy "X", 4'
p FP.copy "X", 4
def inf_list(n)
[n, FPstream.delay{inf_list(n+1)}]
end
def firstsum(n,l)
n == 0 ? 0 : (l[0] + firstsum(n-1, FPstream.force(l[1])))
end
p "firstsum(5, inf_list(1))"
p firstsum(5, inf_list(1))
def integers_from(n)
FPstream.cons (n) {integers_from(n+1)}
end
def integers
integers_from(1)
end
def firstsum2(n, s)
if n == 0
0
else
FPstream.car(s) + firstsum2(n-1, FPstream.cdr(s))
end
end
p "firstsum2(5, FPstream.filter(lambda{|x| x % 2 == 0}, integers))"
p firstsum2(5, FPstream.filter(lambda{|x| x % 2 == 0}, integers))
p "FP.scan(lambda{|a,b| a+b}, 0, 1..5)"
p FP.scan(lambda{|a,b| a+b}, 0, 1..5)
p "FP.group(3, 1..12)"
p FP.group(3, 1..12)
end
[[id:959]] 2002-08-24 00:08:35
遅延評価による無限リスト
単にイテレータブロックを手続きとして返すだけ。
これでいいのだろうか。
def delay(&expr)
expr
end
def force(promise)
if promise.is_a? Proc
promise.call
else
promise
end
end
def inf_list(n)
[n, delay{inf_list(n+1)}]
end
def firstsum(n,l)
n == 0 ? 0 : (l[0] + firstsum(n-1, force(l[1])))
end
p firstsum(5, inf_list(1))
==> 15
[[id:971]] 2002-08-10 20:44:22
リストのグループ化
ｎの倍数個の要素をもつリストを、ｎ個ずつのリストのリストに分割する関数group
def group(n, l)
if l.to_a == [] then []
else
FP.cons(FP.take(n, l), group(n, FP.drop(n, l)))
end
end
----
group 3, (group 2, 1..18)
⇒ [ [[1, 2], [3, 4], [5, 6]], [[7, 8], [9, 10], [11, 12]], [[13, 14], [15, 16], [17, 18]] ]
----
上の式を普通っぽく書くと
- group(3, group(2, 1..18))
です。:D
[[id:1011]] 2002-08-19 15:21:31
先達の技を学ぶ
いやな日記:ソート済の2つの配列をマージする
いやな日記:Ruby/List
[[id:1043]] 2002-08-25 14:31:22
top
recent
HashedWiki version 3 beta
SHIMADA Keiki