ジョセフの日記

Haskellのこととか日常のこととか

前々回の巨大数の単純な拡張

前々回の巨大数の単純な拡張のメモです。


前回、関数の形でLO関数を書きましたが、同様の操作をする本来のリスト操作をする関数の形で書きます。メモなのでHaskellの記法など用いたり、かなり大掴みな説明になります。
g_1([],x) = x
g_1(0:as,x) = f(g_1 (as,x))
g_1(a:as,x) = g_1 (clone(l_1\;,g(as,x)) ++ l_2\;,x)
LO_1(x) = g_1([x,x-1,\cdots,1,0],x)
ここでf(x)=x+1\;,clone(list,n) = list++\cdots++list (n個のlistの結合)であり、M_{n-1} \to M_{n-1}の意味のF_nに対してl_1,l_2はそれぞれF_{n-1}\;,\;F_{n-2},\cdots,F_0に対応する部分を表しています。

ここで次のように再帰的に拡張していきます。
g_n([],list_{n-1},\cdots,list_1,x) = g_{n-1}(list_{n-1},\cdots,list_1,x)
g_n(0:as,list_{n-1},\cdots,list_1,x) = LO_{n-1}(g_{n-1}(as,list_{n-1},\cdots,list_1,x))
g_n(a:as,list_{n-1},\cdots,list_1,x)\\
=g_n(clone (l_1,g_n(as,list_{n-1},\cdots,list_1,x))++l_2 , list_{n-1},\cdots,list_1,x)

LO_n(x) = g_n([x,\cdots,1,0],\cdots,[x,\cdots,1,0],x)\quad(n個の[x,\cdots,1,0])
LLO(x) = LO_x(x)
LLO = LLO^{64} (3)

として二次元リスト操作関数LLO(x)及び二次元リスト操作数LLOが出来るんじゃないかなーと思ってます。
g_nはn個のIntegerリストとIntegerを引数にとっています。ゴチャゴチャして見にくいです。
プログラムの作成や関数の形での理解が出来るのか等の事は後回しということで。