Clojure的计算机代数

15

简化版: 我想找一些Clojure代码,让我可以指定对x的变换(如排列、旋转),以使函数f(x)的值在变换下保持不变,这样我就可以高效地生成一系列满足r = f(x)的x序列。在Clojure中是否有计算机代数方面的进展? 以下是(一个微不足道的)示例。

(defn #^{:domain #{3 4 7} 
         :range #{0,1,2}
         :invariance-group :full} 
          f [x]  (- x x))

我可以调用(preimage f #{0})方法,它会高效地返回#{3 4 7}。自然地,它也能正确地注释目标集合。有什么建议吗?

更长的版本: 我的一个具体问题让我对寻找适用于Clojure的计算机代数开发产生了兴趣。有人能指向这样的项目吗? 我的具体问题涉及查找所有满足F(x) = r的单词组合,其中F是排名函数,r是正整数。在我的特定情况下,f可以计算为以下求和:

F(x) = f(x[0]) + f(x[1]) + ... f(x[N-1])

此外,我还有一组不交集合S = {s_i},使得对于a,b在s中,f(a) = f(b),s在S中。因此,生成所有满足F(x) = r的x的策略应该依赖于F的这种分解和每个s_i下f的不变性。换言之,我要计算包含S元素且总和为r的位置的所有排列,并将它们与每个s_i中元素的所有组合组成。以下是这个过程的简略实现:

(use 'clojure.contrib.combinatorics)
(use 'clojure.contrib.seq-utils)


(defn expand-counter [c]
 (flatten (for [m c] (let [x (m 0) y (m 1)] (repeat y x)))))

(defn partition-by-rank-sum [A N f r]
  (let [M (group-by f A)
    image-A (set (keys M))
    ;integer-partition computes restricted integer partitions,
    ;returning a multiset as key value pairs
    rank-partitions (integer-partition r (disj image-A 0))
    ]
    (apply concat (for [part rank-partitions]
        (let [k (- N (reduce + (vals part)))
          rank-map (if (pos? k) (assoc part 0 k) part) 
          all-buckets (lex-permutations (expand-counter rank-map))
          ]
          (apply concat (for [bucket all-buckets]
        (let [val-bucket (map M bucket)
              filled-buckets (apply cartesian-product val-bucket)]
          (map vec filled-buckets)))))))))

这可以完成任务,但忽略了基本情况。例如,如果关联操作是乘法而不是加法,则必须重新编写某些部分。


请查看2013年的Expresso - Zaz
3个回答

5
下面的系统尚不支持组合数学,但添加它们并不需要太大的努力,已经存在许多优秀的代码,这可能是将其嫁接到平台上的好机会,因为基础知识非常可靠。我希望在这里做一个简短的宣传不会不恰当,这是我所知道的唯一严肃的Clojure CAS,但是,哇,这是一个多么棒的系统...

=======

这对于本主题读者可能很有兴趣,Gerry Sussman的scmutils系统正在移植到Clojure。 这是一个非常先进的计算机代数系统,提供自动微分、文字函数等功能,与Maple非常相似。 它在MIT用于高级动力学和微分几何程序以及一些电气工程方面。它也是Sussman&Wisdom的SICP后续作品SICM使用的系统。 虽然最初是Scheme程序,但这不是直接翻译,而是从头开始重写,以利用Clojure的最佳特性。它被命名为sicmutils,既是对原始版本的致敬,也是对书籍的致敬。 这项出色的工作是Colin Smith的杰作,您可以在https://github.com/littleredcomputer/sicmutils找到它。
我相信这可以成为一个令人惊叹的Clojure计算机代数系统的基础,与其他任何可用的系统竞争。虽然它非常庞大,正如您所想象的那样,还有很多东西需要移植,但基本功能已经基本完成,该系统将进行差异化处理,并很好地处理文字和文字函数。这是一个正在进行中的工作。该系统还使用Sussman提倡的“通用”方法,可以将操作应用于函数,从而创建一个伟大的抽象,简化了符号表示。
> (def unity (+ (square sin) (square cos)))
> (unity 2.0)  ==>  1.0
> (unity 'x)   ==> 1 ;; yes we can deal with symbols
> (def zero (D unity))  ;; Let's differentiate
> (zero 2.0)   ==> 0

SicmUtils引入了两种新的向量类型“up”和“down”(称为“结构”),它们的工作方式几乎符合您对向量的预期,但具有一些特殊的数学(协变,逆变)属性,以及一些编程属性,因为它们是可执行的!

> (def fnvec (up sin cos tan))  => fnvec
> (fnvec 1)   ==> (up 0.8414709848078965 0.5403023058681398 1.5574077246549023)
> ;; differentiated
> ((D fnvec) 1)  ==>  (up 0.5403023058681398 -0.8414709848078965 3.425518820814759) 
> ;; derivative with symbolic argument
> ((D fnvec) 'θ) ==> (up (cos θ) (* -1 (sin θ)) (/ 1 (expt (cos θ) 2)))  

偏微分得到全面支持

> (defn ff [x y] (* (expt x 3)(expt y 5)))
> ((D ff) 'x 'y) ==> (down (* 3 (expt x 2) (expt y 5)) (* 5 (expt x 3) (expt y 4))) 
> ;; i.e. vector of results wrt to both variables

该系统还支持TeX输出、多项式因式分解以及其他许多好东西。然而,很多容易实现的功能仅仅因为缺乏人力资源而未被实现。图形输出和使用Clojure的Gorilla的“记事本/工作表”界面也正在开发中。
我希望这些内容能够激起您的兴趣,访问该网站并尝试一下。您甚至不需要Clojure,可以直接从提供的jar文件运行它。

2
有 Clojuratica,这是 Clojure 和 Mathematica 之间的接口:

http://clojuratica.weebly.com/

请看这位Clojuratica作者的邮件列表帖子
虽然不是CAS,Incanter 也有几个非常好的功能,可能是构建自己想法的良好参考/基础。
关于“例如,如果关联操作是乘积而不是总和,我将不得不重写部分内容”的问题:如果您按照相应的结构编写代码,是否可以通过使用高阶函数并传递关联操作来实现此目标?想想map-reduce。

1

我不知道是否有用Clojure编写的计算机代数系统。然而,对于我的简单数学需求,我发现使用Maxima非常有用,它是用lisp编写的。可以使用s表达式或更高级别的表示与Maxima交互,这非常方便。Maxima还具有一些基本的组合函数,可能是您正在寻找的内容。

如果您坚持要使用Clojure,在短期内,也许在Maxima和Clojure之间来回传递数据可以帮助您实现目标。

从长远来看,我很想看看您的成果!


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接