lengthを使わないでリストを2分割する

リストを２分割する方法

対象となる配列をコピーして(a)と(b)として2つ用意する。 以下の(a),(b)を繰り返し処理する。 (a)1つ目は先頭の要素を取得してしてconsする。残りを次の繰り返しのインプットにする。 (b)2つ目は先頭と次の要素を取得して捨てる。残りを次の繰り返しのインプットにする。 終了条件は、(b)が要素なしになった場合 この時、(a)の残りを、分割する後半部分にする。(a)のconsを処理し、これを分割する前半部分とする。

(a),(b)でリストが小さくなっていくが、(a)は1つずつ、(b)は2つずつ減っていく。

   go [a, b,c,d,e,f]   [a,b,c,d,e,f]
=  go (a:[b,c,d,e,f]) (_:_:[c,d,e,f])
=  first (a:) (go [b, c,d,e,f]  [c,d, e,f] )
=  first (a:) (go (b:[c,d,e,f]) (_:_:[e,f]))
=  first (a:) (first (b:) (go [c, d,e,f]  [e,f  ] ))
=  first (a:) (first (b:) (go (c:[d,e,f]) (_:_:[])))
=  first (a:) (first (b:) (first (c:) (go [d,e,f] []     )))
=  first (a:) (first (b:) (first (c:) (   [],     [d,e,f])))
=  first (a:) (first (b:) ([c],[d,e,f]))
=  first (a:) ([b, c],[d,e,f])
=  ([a, b, c],[d,e,f])