Concurrent Clean : appendの計算量

(++)という演算子がある。これは、リストとリストを結合する演算子だ。

list1 ++ list2
[1,2,3,4] ++ [5,6,7,8]

と使う。
で、最近まで、これの計算量を間違って考えていた。
正格な言語の連想で、

[] ++ [1] ++ [2] ++ [3] ++ [4] ++ [5]

と書くよりも、

reverse [5:[4:[3:[2:[1:[]]]]]]

と書くほうが効率的だと考えていたのだが、それは間違いだった。

ところで、それに関連するが、非正格な言語では、iterativeな書き方は非効率だ。
たとえば、(++)を以下のように実装してはいけない。

(++) l1 l2 = append [] l1 l2
where
    append l0 [] l2 = [l0]++[l2]
    append l0 [l:ls] l2 = append (l0++[l]) ls l2

このように書くと、以下のようなプログラムは停止しなくなる。

Start = hd $ [0..] ++ [1]