[b][size=150][b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/size][/b][br]＜factorial＞[br][/size][/b][br]フィボナッチ数列の一般項は、意外なことに、[br]黄金比にかかわる無理数を使った式になる。[br]くわしい計算はしませんが、[br]漸化式から特性方程式を作り一般項を作ると無理数が残るんだ。[br][br]それに対してNの階乗fact(N)は１からNまでの積だから、一般項は単純だ。[br]だから、再帰関数でも表せるけど、forで十分かけるね。

[color=#0000ff]#再帰を使うならキャッシュを使おう。[br]#==================[br][/color][color=#ff00ff]from functools import cache[br]@cache[br][/color][color=#0000ff]def factorial(n):[br] return n * factorial(n-1) if n else 1[br][br]factorial(100)[br][br]#再帰なしなら、どんどんかけ算して上書きしよう。[br]#==================[br]def fact(n):[br] res=1[br] for i in range(1,n+1):[br] res *=i[br] return res[br]fact(100)[br]#==================[br][br][/color][OUT][br]93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000[br][br][br][br]

geogbraでは[br]fibを再帰を使わずに素早く求めることができた。そのときの手段がIterationListだった。[br]同じようにIterationListやIterationでfactも再帰を使わず求めることができる。[br][br]geogebraにはProductというコマンドがあったね。[br]1から100までの数列をlst=Sequence(100)で作っておき、[br]それの積をProduct(lst)するとfactorial(100)が計算できる。[br][br]でも、有効数字には課題が残った。

pythonにはmathパッケージの関数一覧をリスト表示すると、factorialという関数がすでにありました。[br][b][color=#0000ff][IN][br]#===========[br][/color][/b][b][color=#0000ff]import math[br]print(dir(math))[br]#============[br][/color][/b][OUT][br]['__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'acos', 'acosh', 'asin', 'asinh', 'atan', 'atan2', 'atanh', 'cbrt', 'ceil', 'comb', 'copysign', 'cos', 'cosh', 'degrees', 'dist', 'e', 'erf', 'erfc', 'exp', 'exp2', 'expm1', 'fabs', '[b]factorial[/b]', 'floor', 'fmod', 'frexp', 'fsum', 'gamma', 'gcd', 'hypot', 'inf', 'isclose', 'isfinite', 'isinf', 'isnan', 'isqrt', 'lcm', 'ldexp', 'lgamma', 'log', 'log10', 'log1p', 'log2', 'modf', 'nan', 'nextafter', 'perm', 'pi', 'pow', 'prod', 'radians', 'remainder', 'sin', 'sinh', 'sqrt', 'sumprod', 'tan', 'tanh', 'tau', 'trunc', 'ulp'][br][br][IN][br]#===========[br]from math import factorial as fact[br]fact(100)[br]#============[br]factorial関数だけを factという別名をつけて、簡単に使えます。[br]パッケージがあるときは、何でも自力で作るのではなく、それに乗っかるというときもあってよいでしょう。[br][br]算数、数学と同じようにコード開発でも、[br]知識・技術に乗っかって秒殺する快感とかエレガントさというのもあるでしょう。[br]しかし、それで終わってしまうと、思考が深まりません。[br]フィボナッチ数列よりも扱いやすいということで、階乗計算を使って、[br]くり返し（反復iteration）と自分を呼び出す（再帰recurrsion）の関係をさぐってみましょう。[br]#[IN]C++[br]#=====================[br]int factorial(int n) {[br] int result = 1;[br] for (int i = 1; i <= n; ++i) {[br] result *= i; [br] } [br] return result;[br]}[br]C++でforで反復するとこんな風になるでしょう。[br]これはPythonでもjuliaでも同じようなものです。[br][b][size=150][br]＜productの中身＞[/size][/b][br]haskellでは[br]#=================[br]fact n = product [1..n][br]#=================[br]のように、product関数に１からｎのリストをわたすだけで終了です。[br]ではproduct関数ってどうなっているんでしょう。[br]リストが空なら１を返し、先頭に残りのproductをかければいいですね。[br]だから、再帰関数を使うと、[br][b]product [] =1[br]product (n: ns) = n * product ns[br][/b]と定義できます。[br]数であれば何でもproductできるという一般化をしましょう。[br][br]ghciに尋ねると[br][b]ghci>:info product[br][/b]type Foldable :: (* -> *) -> Constraint[br]class Foldable t where[br] ...[br] product :: Num a => t a -> a[br] -- Defined in ‘Data.Foldable’[br][br][b]ghci> :t product[br]product :: (Foldable t, Num a) => t a -> a[br][/b]と答えてきます。[br]tが畳み込みのできるクラス、aが数のクラスで、数リストt aから数aを返す。[br]だから、次のようにも定義できるのです。[br][b]product = foldl (*) 1[br][/b][br][b][size=150]＜foldlを使おう＞[br][/size][/b]haskellでは、foldlの中はどうなっているのでしょうか？[br]ghci> :t foldl[br]foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b[br]tが畳み込みのできるクラス、（）内は２項演算と数リストt aがあれば、[br]数aのうち演算やリストの左側をbとして、畳み込みを続ける。[br]という型の説明です。これを再帰でかくと次のようになります。[br]foldl f v [ ] = v [br]foldl f v (x: xs) = foldl f (f v x ) xs[br]vを初期値として、演算をｆとする。[br]リストが[ ]になったらｖを返す。（ベースケース）[br]リストの左をｘ、残りをxsとしたら、左ｘにｆをしたものをｖとして[br]残りxsをリストとする。 （再帰ケース）[br][br]foldlを使うと、２項演算をリストにくり返し適用するものなら、[br]簡単に関数定義できますね。[br]（例）[br]関数そのものの定義だから、引数としてのリストは省けます。[br]sum = foldl (+) 0[br]product = foldl (*) 1[br]or = foldl (∨) False[br]and = foldl (∧) True[br]legth = foldl (\n _ -> n+1) 0 [br][br][br][color=#9900ff][u][b][size=150]質問：ほかの言語でのfoldlの活用はどうでしょうか。[br][/size][/b][/u][/color][br]haskellとはちがって、引数はかっこで閉じる必要があるので、見かけは代わります。[br][color=#0000ff]#[IN] julia[br]#=======================[br]function sum(lst)[br] return foldl(+,lst)[br]end[br]function product(lst)[br] return foldl(*,lst)[br]end[br]lst=[1,2,3,4,5][br]println("lst=$lst, sum(lst)=$(sum(lst)),product(lst)=$(product(lst))")[br]#=====================================================[br][/color][OUT][b]lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120[br][/b][br]ちゃんと動きました。[br]次のように[b][color=#0000ff]juliaで数学の関数定義風にかいても動きました。[br][/color][/b]#[IN] julia[br]#=======================[br][b]Sum(lst) = foldl(+,lst)[br]Product(lst)= foldl(*,lst)[br][/b]lst=[1,2,3,4,5][br]println("lst=$lst, Sum(lst)=$(Sum(lst)),Product(lst)=$(Product(lst))")[br][color=#0000ff]#=====================================================[br][/color][OUT][br][b]lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120[br][/b][br]pythonにはfoldlという名前の関数はないが、実態がfoldlと同じreduce関数がある。[br]ただし、パッケージfunctoolsにあるからインポートする。別名foldlをつけてみた。[br][br]残念ながら、reduceの引数は（演算、リスト）ではなく（関数、リスト）だ。[br]だから、+,*のまま渡すのではなく、関数にして渡す。[br]わざわざそのために、関数を外に作るのも手間だから、中にラムダをつかった無名関数[br]にしている。[br]pythonは、ラムダ式の発想を忠実に再現しているが、[br]関数の関数を作ったりしようとすると、[color=#ff0000]簡単な内容なのに難解に見えてしまうのが難点だ。[br][/color][br]#[IN] python[br]#=======================[br][b]from functools import reduce as foldl[br]Sum =lambda lst: foldl(lambda x,y:x+y,lst)[br]Product = lambda lst: foldl(lambda x,y:x*y,lst)[br][/b]lst=[1,2,3,4,5][br]print(f"lst={lst}, Sum(lst)={Sum(lst)},Product(lst)={Product(lst)}")[br]lst=[1, 2, 3, 4, 5], Sum(lst)=15,Product(lst)=120[br][color=#0000ff]#=====================================================[br][/color][[OUT][br][b]lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120[br][br][/b]geogebraの数式、数式処理(CAS)には、関数を自作する機能はあるが、fold,reduceはない。[br]Iteration,IterationListはあくまでも初期値に対する反復計算なので、初期値以外を途中から渡すことはできない。漸化式の発想でしょうね。[br]しかし、sumも、productもすでにあるので、それを使えばよいでしょう。というところか。[br]また、[b]数式処理(CAS)を使うと、nPr,nCrがある[/b]ので、わざわざfactorialを作るところからやらなくても、[br]すぐに順列、組み合わせがすぐに使えるという実用性を重視している感があるね。[br]