■

とりあえず、非決定性計算と論理変数って別になくてもいいんでないの?という疑問が。

非決定性を利用したコードとして、SICPにあるらしい次の問題をCurryで書いてみる。

Baker, Cooper, Fletcher, MillerとSmithは五階建てアパートの異なる階に住んでいる。Bakerは最上階に住むのではない。Cooperは最下階に住むのではない。 Fletcherは最上階にも最下階にも住むのではない。MillerはCooperより上の階に住んでいる。SmithはFletcherの隣の階に住むのではない。FletcherはCooperの隣の階に住むのではない。それぞれはどの階に住んでいるか。

http://mono.kmc.gr.jp/~oxy/w/hiki.cgi?Non+Determinism
http://shugo.net/jit/20051029.html#p02
がネタ元。それぞれHaskellとRubyによるコードがあるので比較すると面白いかも

import Success

abs :: Int -> Int
abs x = if x>0 then x else (-x)

allUniq :: Eq a => [a] -> Bool
allUniq [] = True
allUniq (x:xs) = all (x/=) xs && allUniq xs

solve = 
 findall(\(baker,cooper,fletcher,miller,smith)->
       andC [ baker =:= choose [1,2,3,4,5] ,
              cooper =:= choose [1,2,3,4,5] ,
              fletcher =:= choose [1,2,3,4,5] ,
              miller =:= choose [1,2,3,4,5] ,
              smith =:= choose [1,2,3,4,5] ,
              allUniq [baker,cooper,fletcher,miller,smith] =:= True ,
              (baker /=5) =:= True ,
              (cooper/=1) =:= True ,
              (fletcher/=1 && fletcher/=5)=:=True,
              (miller>cooper)=:=True ,
              (abs(smith-fletcher)/=1)=:=True ,
              (abs(fletcher-cooper)/=1)=:=True ])

andCというのは、単に, x & y & z & ....と書く代わりに、andC[x,y,z,...]と書く関数だと思う(違うかもしれないが)。類似の関数にandSというのがあるけど、何をするのかよく分からない。でも、これって結局、中の人がやってることは、総当りなわけで、そうすると、Haskellとやってることは変わらんよな〜ってことなので、非決定性がキモイかどうかはともかくとして、敢えて、非決定性を言語機能として取り込む実用的なメリットってあんましないような気がしないでもない。

あと、where x freeとかいうのは、論理変数の宣言だったらしい。何も知らず、freeとか付いてるから、自由変数とか思ってたよ。それはいいんだけど、論理変数って使わないよな〜っていう。値取り出すとき、いっつもfindallするから、論理変数の代わりに、ラムダで束縛した変数使う。と思って、サンプルコード眺めてたら、"SEND MORE MONEY" problemを解くCurryのコードで使ってた
http://www.informatik.uni-kiel.de/~curry/examples/CLP/smm.curry

しかし、Zincには、CLPFDモジュールが標準で付いてない上に
http://www.informatik.uni-kiel.de/~pakcs/lib/CDOC/CLPFD.html
から持ってきても、externalがどうとかでうまく動かないのだった。ぬー。

仕方ないので、labelingとか何をしてるか分からんけど適当に自分で書いたら、10分くらいはかかりそうな勢い(´・ω・｀)(+#) とかが高速化に効いてるのか、元のコードでも遅いのかは不明

import Success

domain ls n m =
 andC $ map (\x -> x=:=choose(enumFromTo n m)) ls

allUniq :: Eq a => [a] -> Bool
allUniq [] = True
allUniq (x:xs) = all (x/=) xs && allUniq xs

tenthAdic :: [Int] -> Int
 tenthAdic = aux . reverse
  where
   aux [] = 0
   aux  (x:xs) = x+10*(tenthAdic xs)

smm l =
 l =:= [s,e,n,d,m,o,r,y] &
 domain l 0 9 &
 (s>0)=:=True &
 (m>0)=:=True &
 allUniq l =:= True &
 (tenthAdic[s,e,n,d]+tenthAdic[m,o,r,e]==tenthAdic[m,o,n,e,y]) =:= True
        where s,e,n,d,m,o,r,y free

main= print $ findall(\[s,e,n,d,m,o,r,y]->smm[s,e,n,d,m,o,r,y])

でも、論理変数ないならないで、どうとでもなりそうな気がする

Haskellで汎用的でない回文生成

import Control.Monad.List

pali dom = 
 do { a <- dom;
      b <- dom;
      c <- dom;
      d <- dom;
      e <- dom;
      guard $ a==e;
      guard $ b==d;
      return [a,b,c,d,e] }

main :: IO()
main = print $ pali ['a' , 'b']

Parsecと組み合わせたら、もうちっと何とかなるんでないかな〜

どうも、こういう発想になれてないのか、コードの書き方がいまいちピンとこない。慣れかなー