🔙 Back to Top

Sun Mar 9 18:32:02 JST 2014

関数型プログラミング言語Haskell Part25
http://toro.2ch.net/test/read.cgi/tech/1393313450/

11 名前：デフォルトの名無しさん [sage]： 2014/02/25(火) 20:10:26.83
Data.Function.fix 関数は何のためにあるのでしょうか。
どう使うのでしょうか。

fix :: (a -> a) -> a
fix f = let x = f x in x

12 名前：デフォルトの名無しさん [sage]： 2014/02/25(火) 20:17:14.12
再帰する関数を、それ自身には再帰的定義を含まずに定義するために使う。
Yコンビネータのようなもの（ないし、そのもの）。

13 名前：デフォルトの名無しさん []： 2014/02/25(火) 20:17:35.74
>>11
ループを書きたいけどletやwhereを書くのすら面倒なときに使う
flip fix (0::Int) $ i -> do
　putStrLn $ "total " ++ show i
　n <- readLn
　if n >= 0 then loop $! n + i else return ()

上のを改めて引用

flip fix (0::Int) $ \loop i -> do
  putStrLn $ "total " ++ show i
  n <- readLn
  if n >= 0 then loop $! n + i else return ()

\loop i -> do {} を loop i = do {} と何故か勘違いして脳内型推論にずっと失敗してた。

fix :: (a -> a) -> a

flip は第一引数に a -> b -> c が欲しいから fix の a を b -> c だと解釈することで (HaskellやMLで、第n引数なんて言っていいのかしら)

flip fix :: b -> ((b -> c) -> b -> c) -> c

更に

b = Int
c = IO ()

\loop i の loop という名前は、ただ処理の続行の表現にしか 使ってなくて、call/ccによる大域脱出みたいで、すごくカッコイイ。

\loop i以下をバラして書くと

import Data.Function

main :: IO ()
main =
  fix loop 10
  where
    loop :: (Int -> IO ()) -> Int -> IO ()
    loop cont i =
      if i < 0 then return ()
               else do { print i; cont (i-1) }

多少分かりやすいと思うけど、 ここまで書くならSchemeでもおなじみのただの再帰で

import Data.Function

main :: IO ()
main =
  loop 10
  where
    loop :: Int -> IO ()
    loop i =
      if i < 0 then return ()
               else do { print i; loop (i-1) }

でいいやんな。。。 というか、型に恨み重ねるくらいなら、無理にloop使いたくない。

それよりも、中では一体どんな計算順序を行ってるのか 一回くらい教えてもらわないと気持ち悪い。

Haskellでのループの表現は Data.Function.fix 以外にも

http://hackage.haskell.org/package/base-4.6.0.1/docs/Control-Arrow.html

class Arrow a => ArrowLoop a where
loop :: a (b,d) (c,d) -> a b c

instance ArrowLoop (->) where
loop f b = let (c,d) = f (b,d) in c

使えるかな。

loop f b = fst $ f (b, d)
         = fst $ f (b, snd $ f (b, d))
         = fst $ f (b, snd $ f (b, snd $ f (b, d)))

d の必要がある回数+1 だけ、fが呼ばれる。

f = \(b, d) -> (b-1, d)
loop f 3 = fst $ f (3, d)
         = fst $ (2, d)
         = 2
flip loop 2 $ \(b, d) ->
    (d b, \x -> if x < 0 then [] else x : d (x-1))

= loop f 2
    where
      f (b, d) = (d b, \x -> if x < 0 then [] else x : d (x-1))

= let (c,d) = (d 2, \x -> if .. then [] else x : d (x-1))
    in c

= d 2 where d = \x -> if .. then [] else x : d (x-1)
= 2 : d 1 where d = ...
= 2 : (1 : d 0) where d = ...
= 2 : (1 : 0 : d (-1)) where
= [2, 1, 0]

-- fuck the lazy

ぜってぇこんなの使っても幸せにはならない