いつだってInfinity

Haskell

Infinityの頭文字はIです。

即ち、無限大の愛です。
なんでも無いです忘れてください。

今回もちょいと軽めの話をしましょう。

Haskellの特徴として、遅延評価に加えて、正規形と見なされる制約に「弱頭部正規形」を採用しているという特徴があります。
これは「無限の長さを持つリスト」を定義できる。という事です。Haskellerなら常識ですね。

さて、ここで一つ問題を解いてみましょう、引数が無限リストだった場合Trueを返す関数 isInfinity :: [a] -> Bool を実装してください。




・・・・・・




はい、 そんなプログラムは作れません。
ちゃんと考えるの面倒臭いのでやってないですけど、プログラムの停止性問題あたりを使って厳密に説明できそうです。

さて、無限の長さを持つシーケンスから一つ一つ値を取り出していくような関数を考えましょう。
この関数は、シーケンスの値を永遠に出力し続けます。引数は無限リストである事が前提なので基底部(base case)は不要です。

module Main where

main :: IO ()
main = outputSeq [1..]

outputSeq :: Show a => [a] -> IO ()
outputSeq (x:xs) = putStrLn ("Value = " ++ (show x)) >> outputSeq xs

実行結果：

Value = 1
Value = 2
Value = 3
Value = 4
Value = 5
Value = 6
Value = 7

...

しかし、この関数に有限リスト（例えば[1..6]）を与えた場合、パターンマッチでエラーになってしまいます。

Value = 1
Value = 2
Value = 3
Value = 4
Value = 5
Value = 6
Main.hs: Main.hs:8:1-68: Non-exhaustive patterns in function outputSeq

最低限パターンエラーはマズイという事で、以下のようにエラーメッセージを出すという手も無い事は無いです。

outputSeq :: Show a => [a] -> IO ()
outputSeq [] = error "outputSeq: argument is not infinite list"
outputSeq (x:xs) = putStrLn ("Value = " ++ (show x)) >> outputSeq xs

でもこれ、リストの要素数が100,000,000とか1,000,000,000だった場合、リストの最後尾に辿り着くまでエラーに気づく事ができないので、ぶっちゃけ話にならないです。かといって、予め無限リストかどうか確認するのは、先に上げたとおり不可能ですし...

なんつぅか、そもそもｶｺﾜﾙｲ...

では、もうちょっとマイルドな方法で、引数にcycle関数を適用して強制的に無限リストにするとかどうでしょうか。

outputSeq :: Show a => [a] -> IO ()
outputSeq arg = f $ cycle arg
  where f (x:xs) = putStrLn ("Value = " ++ (show x)) >> outputSeq xs

確かにこれでエラーにはならなくなったけど、引数に対してcycle関数を使うのは、当初outputSeq関数にやらせたかった事では無いのでやはりスマートでは無いです。
とにかくですね、この関数を呼び出すプログラマさんには、明示的に無限の長さを持つリストを渡して欲しいのですよ。なんとかならんでしょうか。


えー...


うん、まー、別に悩むことは無いですね。
今我々が使っている言語はHaskellですし。

InfList.hs

module InfList(
  List,
  fromList,
  toList,
  map,
  take,
  head,
  tail,
  zip,
  zipWith) where

import qualified Prelude as PRE
import Prelude (($))

data List a = List [a]
instance PRE.Functor List where
  fmap = map

fromList :: [a] -> List a
fromList x = List $ PRE.cycle x

toList :: List a -> [a]
toList (List x) = x

map :: (a -> b) -> List a -> List b
map f (List x) = List $ PRE.map f x

take :: PRE.Int -> List a -> [a]
take i (List x) = PRE.take i x

head :: List a -> a
head (List x) = PRE.head x

tail :: List a -> List a
tail (List x) = List $ PRE.tail x

zip :: List a -> List b -> List (a, b)
zip (List x) (List y) = List $ PRE.zip x y

zipWith :: (a -> b -> c) -> List a -> List b -> List c
zipWith f (List x) (List y) = List $ PRE.zipWith f x y

そうです。常に無限リストになるような型を作ってしまうわけですね。

Listのデータコンストラクタはエクスポートしていないので、必然的にfromList関数で値を生成する必要があります、fromList関数は受け取ったリストにcycle関数を適用してからList型にして、返すのでこのモジュールをインポートして作成したList型の値は無限リストである事が保証されるというワケですねー。

module Main where
import qualified InfList as INF

main :: IO ()
main = outputSeq $ INF.fromList [1..6]

outputSeq :: Show a => INF.List a -> IO ()
outputSeq arg = putStrLn ("Value = " ++ (show . INF.head) arg) >> outputSeq (INF.tail arg)

結果的には同じことですが、こうする事で呼び出し元が無限リストを渡すという事を強く意識するようになります。
「うっかり有限リスト渡したら内部でcycleされて予想外の動作になっちまった！！」

という事故が防げるわけですね。

もしかしたら今回のInfListみたいな型って、ブログ主が知らないだけで、既にあるかもしれないですが・・・まぁ、Haskellで設計する場合の思考法の一つとして、参考になれば幸いでつ。
でわでわ。