>>895
それで合ってる。seqを中置で使うのは良く見かける気がする。

seqを使っているのは再帰に入る前にelts_lt_xとelts_greq_xを完全に評価するため。
未評価のelts_greq_xのサンクはxsを参照しているけど、
完全に評価してしまえばただのリストなので、xsへの参照がなくなって、
GCがxsを回収できるようになる。

seq A Bの値はBと同じだけど、この式を評価する時はまずAを評価して、
その結果を捨て、改めてBを評価する。
length elts_lt_x `seq` 本体
を評価するときは、まずelts_lt_xの長さを求めることになるが、
リストの長さを求めるにはリスト全体を評価する必要がある。
結局、本体が評価される前にelts_lt_xが完全に評価される。

lengthが必要な理由には、seqの仕様が関わってくる。
seq A Bが評価されるとき、Aは弱冠頭正規形(weak head normal form, WHNF)まで簡約される。
WHNFというのは、最も外側のデータ構築子が確定した形。
例えば1+2や[1,2]++[3,4]はWHNFじゃないけど、3や1:([2]++[3,4])はWHNF。
だから、lengthを使わずに
elts_lt_x `seq` 本体
のように定義すると、例えば
elts_lt_x = [y | y <- [1, 2, 3, 4], y < 5]
のとき、これを
elts_lt_x = 1 : [y | y <- [2, 3, 4], y < 5]
と簡約したら、この段階でWHNFに達したことになり、評価が終わってしまう。
これだと、xs(ここでは[2, 3, 4])への参照が残っていて、GCがxsを回収できない。