From haskell-jp=return=sinara=blade.nagaokaut.ac.jp@quickml.com Sat Dec 20 02:05:51 2003 X-cmail-status: Active X-UIDL: -T1!!NXo"!78<"!jmh"! Return-Path: Received: from kankan.nagaokaut.ac.jp (kankan.nagaokaut.ac.jp [133.44.2.24]) by blade.nagaokaut.ac.jp (8.12.3+3.5Wbeta/8.12.6/Debian-8) with ESMTP id hBJH5kV0012713 for ; Sat, 20 Dec 2003 02:05:51 +0900 Received: from funfun.nagaokaut.ac.jp (funfun.nagaokaut.ac.jp [133.44.2.201]) by kankan.nagaokaut.ac.jp (Postfix) with ESMTP id 343345918 for ; Sat, 20 Dec 2003 02:07:21 +0900 (JST) Received: from localhost (localhost.nagaokaut.ac.jp [127.0.0.1]) by funfun.nagaokaut.ac.jp (Postfix) with ESMTP id 12B82F04893 for ; Sat, 20 Dec 2003 02:07:21 +0900 (JST) Received: from voscc.nagaokaut.ac.jp (voscc.nagaokaut.ac.jp [133.44.1.100]) by funfun.nagaokaut.ac.jp (Postfix) with ESMTP id 495DEF04891 for ; Sat, 20 Dec 2003 02:07:20 +0900 (JST) Received: from quickml.com (quickml.com [133.138.2.9]) by voscc.nagaokaut.ac.jp (Postfix) with ESMTP id 1A06263003F for ; Sat, 20 Dec 2003 02:07:20 +0900 (JST) Received: from kanakan.csl.sony.co.jp (quickml.com [133.138.2.9]) by quickml.com (Postfix) with ESMTP id 69ABE4598; Sat, 20 Dec 2003 02:07:14 +0900 (JST) Received: from quickml.com (quickml.com [133.138.2.9]) by localhost (QuickML) with ESMTP; Sat, 20 Dec 2003 02:07:14 +0900 Received: from kencho.tom.sfc.keio.ac.jp (kencho.tom.sfc.keio.ac.jp [133.27.175.5]) by quickml.com (Postfix) with ESMTP id 70A864596 for ; Sat, 20 Dec 2003 02:07:13 +0900 (JST) Received: (qmail 12808 invoked by uid 60000); 20 Dec 2003 02:08:00 +0900 Received: from sakai@tom.sfc.keio.ac.jp by kencho by uid 64011 with qmail-scanner-1.20rc3 (clamscan: 0.60. Clear:RC:1:SA:0(-1.9/7.0):. Processed in 0.51814 secs); 19 Dec 2003 17:08:00 -0000 Received: from unknown (HELO localhost) ([133.27.175.5]) (envelope-sender ) by kencho.tom.sfc.keio.ac.jp (qmail-ldap-1.03) with SMTP for ; 20 Dec 2003 02:08:00 +0900 Date: Sat, 20 Dec 2003 02:02:38 +0900 (JST) Message-Id: <20031220.020238.78713531.sakai@tom.sfc.keio.ac.jp> To: haskell-jp@quickml.com From: Masahiro Sakai (=?iso-2022-jp?B?GyRCPHIwZkAvTTUbKEI=?=) In-Reply-To: <6.0.0.20.2.20031219184220.03d4c868@blade.nagaokaut.ac.jp> References: <6.0.0.20.2.20031216185312.0358b450@blade.nagaokaut.ac.jp> <20031217221145.AF38.NOBU_TOYOFUKU@nifty.com> <6.0.0.20.2.20031219184220.03d4c868@blade.nagaokaut.ac.jp> X-Mailer: Mew version 4.0.60 on Emacs 21.3.1 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Multipart/Mixed; boundary="--Next_Part(Sat_Dec_20_02_02_38_2003_726)--" Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on kencho.tom.sfc.keio.ac.jp X-Spam-Level: X-Spam-Status: No, hits=-1.9 required=7.0 tests=FAKEDWORD_ATMARK, ISO2022JP_BODY autolearn=no version=2.60 Subject: [haskell-jp:294] Re: =?iso-2022-jp?B?GyRCSVRGMEVAJEgkNyRGJE46RjUiJVcbKEI=?= =?iso-2022-jp?B?GyRCJW0lMCVpJWAbKEI=?= Reply-To: haskell-jp@quickml.com X-Mail-Count: 294 Precedence: bulk X-ML-Address: haskell-jp@quickml.com X-ML-Name: haskell-jp X-ML-Info: http://QuickML.COM/ X-QuickML: true X-Virus-Scanned: by AMaViS snapshot-20020531 Status: RO ----Next_Part(Sat_Dec_20_02_02_38_2003_726)-- Content-Type: Text/Plain; charset=iso-2022-jp Content-Transfer-Encoding: 7bit さかいです。 From: Shin-ichiro HARA Date: Fri, 19 Dec 2003 18:57:30 +0900 > 原です。 > > > 豊福です。 > >これのレポート問題 > >http://www.kurims.kyoto-u.ac.jp/~hassei/questions.pdf > >の問題２の答えの X3 がわからない（手作業でやると手に負えそう > >にないような気がする）のですが解いた人いませんか。 > > 確かにこれはややこしい。きれいな答は出ないんでしょう。 > ここでリストアップする関数を Hakell で披露するとかっこいい > んだけど、、、力及ばず。(^^; 試しに、ちょー手抜きプログラムをRubyで書いて計算してみました。 原さんの finite-set を使っています。 http://blade.nagaokaut.ac.jp/~sinara/ruby/math/ また、有限集合上の関数は単調ならば連続になることが知られているので、 単調性しかチェックしてません。 じゃ、Haskell版は誰か他の人よろしく :-P -- 酒井 政裕 / Masahiro Sakai -- ML: haskell-jp@quickml.com 使い方: http://QuickML.com/ ----Next_Part(Sat_Dec_20_02_02_38_2003_726)-- Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="poset.rb" require 'finite-set' require 'finite-map' class Poset def initialize(underlying_set, <_eq) lt_eq = lambda{|a,b| a <= b } unless lt_eq @underlying_set = underlying_set @lt_eq = lt_eq end attr_reader :underlying_set def lt_eq(a,b) @lt_eq.call(a,b) end def **(other) ary = other.underlying_set.to_a s = Set[] f = Map.phi(self.underlying_set) func = lambda{|i| if i < ary.size c = ary[i] @underlying_set.each{|d| f[c] = d func.call(i+1) } else if other.underlying_set.all?{|a| other.underlying_set.all?{|b| lt_eq(f[a],f[b]) or not other.lt_eq(a,b) } } s.push(MonotonicFunction.new(f.dup, other, self)) end end } func.call(0) =begin s = (@underlying_set ** other.underlying_set).select_s{|f| other.underlying_set.all?{|a| other.underlying_set.all?{|b| lt_eq(f[a],f[b]) or not other.lt_eq(a,b) } } }.map_s{|f| MonotonicFunction.new(f, other, self) } =end =begin Poset.new(s) =end elem_to_upper_closure = Hash.new s.each{|f| elem_to_upper_closure[f] = s.select_s{|g| f <= g } } Poset.new(s){|f,g| elem_to_upper_closure[f].member?(g) } end end class MonotonicFunction def initialize(underlying_map, dom, cod) @underlying_map = underlying_map @dom = dom @cod = cod end attr_reader :underlying_map attr_reader :dom attr_reader :cod def [](e) @underlying_map[e] end def <=(other) @dom.underlying_set.all?{|a| @cod.lt_eq(self[a], other[a]) } end end A = Poset.new(Set[0,1,2]) def F(x) A**x end X0 = Poset.new(Set[0]) p X0.underlying_set.size #=> 1 X1 = F(X0) p X1.underlying_set.size #=> 3 X2 = F(X1) p X2.underlying_set.size #=> 10 X3 = F(X2) p X3.underlying_set.size #=> 126 ----Next_Part(Sat_Dec_20_02_02_38_2003_726)----