日々の流転

λ. となりの８０１ちゃん

なんか、「となりの８０１ちゃん」というブログを紹介されたのだが、これ凄いね。

λ. ICPC国内予選

私は今年はもう参加できないなんだよなぁ。去年参加したときは面倒くさいとか思ってたが、悔しかったのでまた挑戦したかった。

λ. concatN

<URL:http://d.hatena.ne.jp/lethevert/20060630/p3> より。

ぁゃιぃ拡張機能を使うと出来ないこともない気がする。以下のコードの元ネタはOlegさんの Deepest functor 。なお、私はどうしてこれでうまくいくのかいまだに良くわかってない。

{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
{-# OPTIONS -fallow-overlapping-instances #-}
module ConcatN where

data Atom

-- Check if a type is a collection type. This is the only typeclass that
-- needs overlapping instances
class IsCollection  t coll | t -> coll
instance IsCollection (m a)       (m ())
instance TypeCast Atom coll => IsCollection t coll

-- our common working horse
class TypeCast   a b   | a -> b, b->a   where typeCast   :: a -> b
class TypeCast'  t a b | t a -> b, t b -> a where typeCast'  :: t->a->b
class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b
instance TypeCast'  () a b => TypeCast a b where typeCast x = typeCast' () x
instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast''
instance TypeCast'' () a a where typeCast'' _ x  = x

class ConcatN a c | c -> a where
    concatN :: c -> [a]

instance (IsCollection c coll, ConcatN' coll a c) => ConcatN a c where
    concatN = concatN' (undefined::coll)

class ConcatN' coll a c | coll c -> a where
    concatN' :: coll -> c -> [a]

instance ConcatN' Atom a a where
    concatN' _ a = [a]

instance (ConcatN a c) => ConcatN' [()] a [c] where
    concatN' _ = concatMap concatN

test1 = concatN [[[True]],[[False,True]],[]]
test2 = concatN [[1::Int,2,3],[4]]

深さを指定してconcat

稲葉さんのとこで色々なコードが紹介されていたので、私も少しバリエーションを。深さを指定してconcatするなら、私ならこんな感じで書くかな。

data Z   = Z
data S n = S n

class ConcatN a n l | a n -> l where
    concatN :: n -> l -> [a]

instance ConcatN a Z [a] where
    concatN _ = id

instance ConcatN a n l => ConcatN a (S n) [l] where
    concatN _ = concatMap (concatN (undefined :: n))

さらに、型クラスではなくGADTを使ったバージョン。

data N a l where
    Z :: N a [a]
    S :: N a l -> N a [l]

concatN :: N a l -> l -> [a]
concatN Z     = id
concatN (S n) = concatMap (concatN n)

λ. 某氏の筆箱の中身

まるで、雑多なものが沢山入っていて、まるで植芝理一の漫画のようだ。 感動。