factをやろう
１．再帰なしに階乗計算できる？
このワークシートはMath by Codeの一部です。
＜factorial＞
フィボナッチ数列の一般項は、意外なことに、
黄金比にかかわる無理数を使った式になる。
くわしい計算はしませんが、
漸化式から特性方程式を作り一般項を作ると無理数が残るんだ。
それに対してNの階乗fact(N)は１からNまでの積だから、一般項は単純だ。
だから、再帰関数でも表せるけど、forで十分かけるね。
#再帰を使うならキャッシュを使おう。
#==================
from functools import cache
@cache
def factorial(n):
return n * factorial(n-1) if n else 1
factorial(100)
#再帰なしなら、どんどんかけ算して上書きしよう。
#==================
def fact(n):
res=1
for i in range(1,n+1):
res *=i
return res
fact(100)
#==================
[OUT]
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
階乗はIterationListかProductか？
geogbraでは
fibを再帰を使わずに素早く求めることができた。そのときの手段がIterationListだった。
同じようにIterationListやIterationでfactも再帰を使わず求めることができる。
geogebraにはProductというコマンドがあったね。
1から100までの数列をlst=Sequence(100)で作っておき、
それの積をProduct(lst)するとfactorial(100)が計算できる。
でも、有効数字には課題が残った。
２．再帰と反復
pythonにはmathパッケージの関数一覧をリスト表示すると、factorialという関数がすでにありました。
[IN]
#===========
import math
print(dir(math))
#============
[OUT]
['__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', 'factorial', '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']
[IN]
#===========
from math import factorial as fact
fact(100)
#============
factorial関数だけを factという別名をつけて、簡単に使えます。
パッケージがあるときは、何でも自力で作るのではなく、それに乗っかるというときもあってよいでしょう。
算数、数学と同じようにコード開発でも、
知識・技術に乗っかって秒殺する快感とかエレガントさというのもあるでしょう。
しかし、それで終わってしまうと、思考が深まりません。
フィボナッチ数列よりも扱いやすいということで、階乗計算を使って、
くり返し（反復iteration）と自分を呼び出す（再帰recurrsion）の関係をさぐってみましょう。
#[IN]C++
#=====================
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; ++i) {
result *= i;
}
return result;
}
C++でforで反復するとこんな風になるでしょう。
これはPythonでもjuliaでも同じようなものです。
＜productの中身＞
haskellでは
#=================
fact n = product [1..n]
#=================
のように、product関数に１からｎのリストをわたすだけで終了です。
ではproduct関数ってどうなっているんでしょう。
リストが空なら１を返し、先頭に残りのproductをかければいいですね。
だから、再帰関数を使うと、
product [] =1
product (n: ns) = n * product ns
と定義できます。
数であれば何でもproductできるという一般化をしましょう。
ghciに尋ねると
ghci>:info product
type Foldable :: (* -> *) -> Constraint
class Foldable t where
...
product :: Num a => t a -> a
-- Defined in ‘Data.Foldable’
ghci> :t product
product :: (Foldable t, Num a) => t a -> a
と答えてきます。
tが畳み込みのできるクラス、aが数のクラスで、数リストt aから数aを返す。
だから、次のようにも定義できるのです。
product = foldl (*) 1
＜foldlを使おう＞
haskellでは、foldlの中はどうなっているのでしょうか？
ghci> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
tが畳み込みのできるクラス、（）内は２項演算と数リストt aがあれば、
数aのうち演算やリストの左側をbとして、畳み込みを続ける。
という型の説明です。これを再帰でかくと次のようになります。
foldl f v [ ] = v
foldl f v (x: xs) = foldl f (f v x ) xs
vを初期値として、演算をｆとする。
リストが[ ]になったらｖを返す。（ベースケース）
リストの左をｘ、残りをxsとしたら、左ｘにｆをしたものをｖとして
残りxsをリストとする。 （再帰ケース）
foldlを使うと、２項演算をリストにくり返し適用するものなら、
簡単に関数定義できますね。
（例）
関数そのものの定義だから、引数としてのリストは省けます。
sum = foldl (+) 0
product = foldl (*) 1
or = foldl (∨) False
and = foldl (∧) True
legth = foldl (\n _ -> n+1) 0
質問：ほかの言語でのfoldlの活用はどうでしょうか。
haskellとはちがって、引数はかっこで閉じる必要があるので、見かけは代わります。
#[IN] julia
#=======================
function sum(lst)
return foldl(+,lst)
end
function product(lst)
return foldl(*,lst)
end
lst=[1,2,3,4,5]
println("lst=$lst, sum(lst)=$(sum(lst)),product(lst)=$(product(lst))")
#=====================================================
[OUT]lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120
ちゃんと動きました。
次のようにjuliaで数学の関数定義風にかいても動きました。
#[IN] julia
#=======================
Sum(lst) = foldl(+,lst)
Product(lst)= foldl(*,lst)
lst=[1,2,3,4,5]
println("lst=$lst, Sum(lst)=$(Sum(lst)),Product(lst)=$(Product(lst))")
#=====================================================
[OUT]
lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120
pythonにはfoldlという名前の関数はないが、実態がfoldlと同じreduce関数がある。
ただし、パッケージfunctoolsにあるからインポートする。別名foldlをつけてみた。
残念ながら、reduceの引数は（演算、リスト）ではなく（関数、リスト）だ。
だから、+,*のまま渡すのではなく、関数にして渡す。
わざわざそのために、関数を外に作るのも手間だから、中にラムダをつかった無名関数
にしている。
pythonは、ラムダ式の発想を忠実に再現しているが、
関数の関数を作ったりしようとすると、簡単な内容なのに難解に見えてしまうのが難点だ。
#[IN] python
#=======================
from functools import reduce as foldl
Sum =lambda lst: foldl(lambda x,y:x+y,lst)
Product = lambda lst: foldl(lambda x,y:x*y,lst)
lst=[1,2,3,4,5]
print(f"lst={lst}, Sum(lst)={Sum(lst)},Product(lst)={Product(lst)}")
lst=[1, 2, 3, 4, 5], Sum(lst)=15,Product(lst)=120
#=====================================================
[[OUT]
lst=[1, 2, 3, 4, 5], sum(lst)=15,product(lst)=120
geogebraの数式、数式処理(CAS)には、関数を自作する機能はあるが、fold,reduceはない。
Iteration,IterationListはあくまでも初期値に対する反復計算なので、初期値以外を途中から渡すことはできない。漸化式の発想でしょうね。
しかし、sumも、productもすでにあるので、それを使えばよいでしょう。というところか。
また、数式処理(CAS)を使うと、nPr,nCrがあるので、わざわざfactorialを作るところからやらなくても、
すぐに順列、組み合わせがすぐに使えるという実用性を重視している感があるね。