>   計算オーダより気になっていることなのですが xs の producer
> が止まっているとき最終的に length xs <= n になるにもかかわらず
> otherwise の方に進むということはないのですか。

いえ、この場合、演算子 <= はオペランドとして Int 型の確定した値を要求
しますので、length xs が確定しないうちは判定がおこりません。

> と書いてる途中に新しいメールが、
> 
> >>   xs が確定していなくても「length xs <= n」をある程度計算
> >> できるんでしたっけ。
> > いえ、improving value のような仕組を明示的に定義しないとできません。
> > 
> > ivLength :: [a] -> [Int]
> > ivLength = iter 0
> >   where iter n []     = []
> >         iter n (_:ls) = n:iter (n+1) ls
> > tailn n xs | elem (n+1) (ivLength xs) = tailn n (tail xs)
> >            | otherwise                = xs

おっと、寝惚けたことやってしまった。
tailn 定義の一行目の elem の第一引数は n+1 ではなく n ですね。

ちょっとコードをまとめてみました。

\begin{code}

rtailn :: Int -> [a] -> [a]            -- Reverse version
rtailn n = reverse . (take n) . reverse

ttailn :: Int -> [a] -> [a]            -- Toyofuku version
ttailn n ls = difftail ls (drop n ls)
  where difftail hs []         = hs
        difftail (_:hs) (_:ts) = difftail hs ts

htailn :: Int -> [a] -> [a]            -- Hayakawa version
htailn n xs | length xs <= n = xs
            | otherwise      = htailn n (tail xs)

itailn :: Int -> [a] -> [a]            -- Improving Value ? version
itailn 0 _  = []
itailn n [] = []
itailn n xxs@(_:xs) | elem n (ivLength xxs) = itailn n xs
                    | otherwise             = xxs
  where 
    ivLength = iter 0
    iter _ [] = []
    iter n (_:ls) = n : iter (n+1) ls

\end{code}

比較をするといいかも。
hugs では +s オプションで、評価にかかったリダクション数と使用セル数がでます。
ただし、セル使用量のピークなどはでません。プロファイルをとる必要があります。

--
Nobuo Yamashita                 mailto:nobsun / sampou.org
  I love programming.           http://www.sampou.org/
  I love pencil puzzles.        http://www.puzzle.jp/

--
ML: haskell-jp / quickml.com
使い方: http://QuickML.com/