豊福です。

nobsunさん
> tailn :: Int -> [a] -> [a]
> tailn n ls = difftail ls (drop n ls)
>   where difftail hs []         = hs
>         difftail (_:hs) (_:ts) = difftail hs ts

  むむむむむ、スマートだなあ。

>> 「haskell 差分リスト」で検索してもどこのページも引っ掛からないので不安です。
> このあたりのテクニックは、deforestation の範疇かな。

  deforestation は初めて聞きました(伐採?)。producer と
consumer 関係のやつですか。
  (x:xs) のパターンは(当り前ですが)よく見かけるのですが、
head と tail をペアで持ち歩く例を入門編などで見た記憶が
ありません。どこかにないでしょうか。

>> tailn n xs | length xs <= n = xs
>>            | otherwise      = tailn n (tail xs)
>
> これだと、計算オーダが O(n^2) になると思いますが。。。

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

と書いてる途中に新しいメールが、

>>   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

  すぐには理解できないので一晩寝てからまた。
---
                        豊福
                        ttoyofukujp / yahoo.co.jp

__________________________________________________
Do You Yahoo!?
Yahoo! BB is Broadband by Yahoo!  http://bb.yahoo.co.jp/


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