[Haskell-ELTE] Mivel etessem a függvényemet? :)

[Dévai Gergely]

Sziasztok!

Adott egy tetszőleges adattípus, például ez:

data Foo = Bar | Baz Foo Foo

A feladat az

isConstant :: (Foo -> Foo) -> Bool

függvény megírása, amelynek el kell döntenie, hogy az argumentuma 
konstans függvény-e.

Nem általában szeretném ezt megoldani, hanem csak speciális tulajdonságú 
függvények esetén kell jól működnie.

Nevezzünk egy függvényt "konstruktor-szerű" függvénynek, ha nem cincálja 
szét az argumentumát, legfeljebb beleteszi az eredménybe, mint egy 
építőkockát.
Példák konstruktor-szerű függvényekre: id, \x -> Bar, \x -> Baz x Bar
Példa nem konstruktor-szerű függvényre:
\x -> case x of
	Bar -> Baz Bar Bar
	Baz y _	-> y

Sajnos nem tudom, hogy "igazából" hogy hívják ezt a függvény-osztályt, 
de szeretném tudni. :)

A feladat tehát az, hogy konstruktor-szerű függvényekre jól működjön az 
isConstant.

1. megoldás:
Hozzáveszünk egy Dummy alternatívát az adattípushoz, megetetjük a 
függvényt egy Dummy-val, majd megnézzük az eredményt, hogy belekerült-e 
a Dummy.

data Foo
     = Bar | Baz Foo Foo | Dummy

isConstant :: (Foo -> Foo) -> Bool
isConstant f = dummyLess $ f Dummy where
     dummyLess Bar = True
     dummyLess (Baz f1 f2) = dummyLess f1 && dummyLess f2
     dummyLess Dummy = False

Ez a megoldás azért nem tetszik, mert hozzá kellett nyúlni az 
adattípushoz, ráadásul biztosítani kell, hogy más célra a Dummy-t 
véletlenül se használják.

2. megoldás:
Az adattípus érintetlenül marad, a függvényt egy kivétellel etetjük meg, 
majd bejárjuk az eredményt és elkapjuk az esetlegesen fellépő kivételt.

import Control.Exception
import System.IO.Unsafe

data Foo
     = Bar | Baz Foo Foo

instance Exception () where
     toException () = SomeException ()
     fromException _ = Just ()

walk :: Foo -> IO Int
walk Bar = return 1
walk (Baz f1 f2) = do
     x <- walk f1
     y <- walk f2
     return $ x+y

isConstant :: (Foo -> Foo) -> Bool
isConstant f = unsafePerformIO $ do
     x <- try $ walk $ f $ throw () :: IO (Either () Int)
     case x of
         Right _ -> return True
         Left _  -> return False

Ez a megoldás azért nem tetszik, mert unsafePerformIO-zik. Épp ezért a 
helyességéről sem vagyok meggyőződve.

Tudtok-e jobb megoldást?

Köszi,
Gergő