whileをやろう
プログラミングの鍵は途中脱出
このワークシートはMath by Codeの一部です。
＜whileをやろう＞
ここまで、juliaでやれていたことはgeobebraでもできた。
これは、関数・宣言型の記述、リスト中心という方向でも
順次、反復、条件分岐の３要素が実現できたからだ。
これで、これで安心というわけにはいかない。
forはsequenceコマンドリスト化できたけれども
whileはまだ置き換えられていない。
たとえば、whileでも終わりが見えているものなら
終わりまでの範囲でfor文で追いかけられる。
しかし、終わりが見えないで、途中で反復を脱出するwhile型を、関数型に翻訳するには
どうしたらよいだろうか。
whileを使いそうになる例を使って考えてみよう。
100以下の素数を列挙したいときどうするか。
よくあるのは、
2からNの平方根未満の整数ｐまでで順番にNをわり算してみる。
まずは、約数リストを作り、それを数えて約数の個数が２だったら素数といえる。
この考え方でプログラミングしてみよう。
julia
#================================================
#ｎの約数リストを作る関数
function divs(n)
#nの約数を速く求めるためには、ルートn以下の整数までで割ればよい。
divisors = []
res = round(n^0.5)
#小数表示の整数を整数表示にする
lim = Int(res)
for p= 1:lim
if n % p ==0
push!(divisors,p)
#juliaの整数の商は÷でよい。
if (p != n ÷ p)
push!(divisors,n ÷ p)
end
end
end
return divisors
end
function isPrime(N)
if length(divs(N))==2
return true
else
return false
end
end
filter(x -> isPrime(x),2:100)
#================================================
[OUT]
25-element Vector{Int64}:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
これを関数型にするとなんと１行でかける。
#========================================
filter(n->length(filter( m -> n % m==0,1:n))==2, 2:100)
#=======================================
順次的な調査はしてないから、ｎの平方根未満までを調べるというような制約はいらない。
これをgeogebraでやることもできる。
#================================================================
prims=KeepIf(Length(KeepIf(Mod(k,n)≟0,n,Sequence(k)))≟2,k,Sequence(100)
#================================================================
さて、手続き型でも、約数リストを作らないことで短縮できるね。
#================================================
function prime(n)
lim = Int(round(n^0.5))
for num in 2:lim
if n % num ==0
return false
end
end
return true
end
filter(x -> prime(x),2:100)
#================================================
Nの平方根未満の整数までで割り算を止めているのは割り算回数の節約のためだ。
もし、無駄を承知なら次のようなwhile文で延々とわり算しても判定はできる。
約数が見つかったときにwhileを脱出して関数も終了すればいいのだから。
100までの素数を１行で求める方法
＜whileの反復脱出をなしにしたい＞
よくあるwhile型の反復脱出プログラムを書こうとしたら、
このgeobebraテキストアプリが勝手に改造するバグがあるので、
かけない。
例えば、簡単にいうと、res=trueにしておく。
while resとかを先頭にかく。
中に、約数があればres=falseにして反復を脱出してreturn resする。
では、whileなしで関数型にしよう。
まずは、100で実験してみる。
[IN]julia
# n=100に対して、
# 2から100-1までのリストを作る。その要素である数ｍで100を割る。
# 割り切れたら0,それ以外なら1をマッピングする。
# こうやって、脱出条件となる情報をひたすらメモするのなら、
# 関数型・リスト型で行けそうだ！
n=100
try100=map(m-> n % m==0 ? 1 : 0 ,2:n-1)
println(try100)
#=====================
[OUT]
[1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
次は本番。
[IN]julia
# 2から100までの数nに対して、
# 2からn-1までのリストを作る。その要素である数mでnを割る。
# 割り切れたら0,それ以外なら1をマッピングする。0か1を要素とする99個のリストのリストができる。
# １つ１つのリストに対して、(n、0か1を合計）というタプルに変換する。
# nが素数なら2からn-1の間に約数がないから、合計は０になる。
# (n,0)のときに、nが素数になる。
res=map(n->(n,sum(map(m-> n % m==0 ? 1 : 0 ,2:n-1))),2:100)
println(res)
#=====================
[OUT]
[(2, 0), (3, 0), (4, 1), (5, 0), (6, 2), (7, 0), (8, 2), (9, 1), (10, 2), (11, 0), (12, 4), (13, 0), (14, 2), (15, 2), (16, 3), (17, 0), (18, 4), (19, 0), (20, 4), (21, 2), (22, 2), (23, 0), (24, 6), (25, 1), (26, 2), (27, 2), (28, 4), (29, 0), (30, 6), (31, 0), (32, 4), (33, 2), (34, 2), (35, 2), (36, 7), (37, 0), (38, 2), (39, 2), (40, 6), (41, 0), (42, 6), (43, 0), (44, 4), (45, 4), (46, 2), (47, 0), (48, 8), (49, 1), (50, 4), (51, 2), (52, 4), (53, 0), (54, 6), (55, 2), (56, 6), (57, 2), (58, 2), (59, 0), (60, 10), (61, 0), (62, 2), (63, 4), (64, 5), (65, 2), (66, 6), (67, 0), (68, 4), (69, 2), (70, 6), (71, 0), (72, 10), (73, 0), (74, 2), (75, 4), (76, 4), (77, 2), (78, 6), (79, 0), (80, 8), (81, 3), (82, 2), (83, 0), (84, 10), (85, 2), (86, 2), (87, 2), (88, 6), (89, 0), (90, 10), (91, 2), (92, 4), (93, 2), (94, 2), (95, 2), (96, 10), (97, 0), (98, 4), (99, 4), (100, 7)]
#これでは、素数以外もまざるから、タプルの第２要素==0のときの第1要素だけを抜き出せば、
素数一覧になる。
map(x->x[1],filter(x->x[2]==0,res))
これは、次のようにgeogebraでもいける。
Whileを使わなくても脱出条件の結果の記録を使えばいいんだね。
質問：他のwhile脱出以外に、回数のわからない反復のコード化はできないのでしょうか。
whileを使う文脈は、調べる範囲や回数が未定な状況があるときです。
調査範囲の上限や最大値が事前にわかっていれば、そこまで回せがよいのですが、
終了条件を達成するための調査範囲の上限がわからないからこそ、実際にまわしてみるわけです。
ということはリストが無限のサイズならば、リスト処理が可能になりますね。
本当は無限ではないのですが、特に決めておかないという形式の定義ならば無限も定義できます。
haskellでは無限の自然数列を定義しておき、
--[Haskell]============
infiniteList :: [Int]
infiniteList = [1..]
--==================
ghci>take 1000 infiniteList
のように1000まで取り出すときに初めて評価する、のろい評価、遅延Lazy評価という機構がある。
フィボナッチ数列も遅延評価で作れる。
なおzipwithは他のよくある関数の表示でかくと、zipwith(２項演算、リスト１，リスト２）となり、
リスト１，リスト２をzipしてリストを作るときに、
タプルのリストを作るのではなく２項演算をした結果のリストを作るということだ。
また、tail リストは、リストの２番目を先頭にしたリストのことだね。
だから、１個ずらして＋をしたリストを続けて作ることになるね。
でも、実行時に評価するし、実行しないときは終了の位置は関係ない。
takeするときだけ実行するからだ。
--[Haskell]============
fibo :: [Integer]
fibo = 1 : 1 : zipWith (+) fibo (tail fibo)
--==================
ghci> take 100 fibo
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075]
遅延評価を使うと、エラトステネスのふるいsieveの考え方が
そのままコードになる。
素数は２から始まるので２以上の整数リスト[2..]にふるいsieveにかける。その結果が素数たちprimesだ。
そこで、ふるいsieve(先頭p: 残りxs）は、pのあとは、xsのうち数pで割り割り切れないものを残す。
--[Haskell]============
primes :: [Integer]
primes = sieve [2..]
where
sieve (p:xs) = p : sieve (filter ((/=0) . (`mod` p)) xs)
--==================
ghci> take 100 primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]
質問：この遅延評価の考え方をpythonやjuliaでも使えますか。
普通にyieldとnextのペアで実現できます。
whileの無限ループの関数を作り、
return の代わりにyieldにして、戻り値を表します。
もどった値を入れた変数にnext()をすることで、必要な回数だけ無限関数を有限回数で利用するという
理屈です。
while脱出型ではないですが、while停止型です。
pythonでもwhile機構を使わないと無限を表すことができないということでした。
[IN]Python
#==============
def fibo():
a, b = 1, 1
while True:
yield a
a, b = b, a + b
f = fibo()
for i in range(1,101):
print(next(f),end=",")
#==============
[OUT]
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,
juliaにも「すぐに実行しないイテレータ」を作るしくみgenerator()とyield文があるのですが、
有限範囲で作ってから取り出すしくみなので、forを回したりメモ化の方が簡単です。
いろいろお膳立てすると無限と遅延が両立できるようです。