Haskell library like SymPy? [closed]

Question

I need to manipulate expressions like 1 + sqrt(3) and do basic arithmetic like addition, subtraction, and division. I'd like the result to be in some sort of canonical form so that it can be used as a key in a map. Turning 1 + sqrt(3) into a float is not feasible due to roundoff problems.

I used SymPy for this task in Python. Is there an equivalent native library for Haskell?

Opiate

Do you want √2 - 1 == 1 / (√2 + 1)? – Kreiker

Answer 1

Please check out the numbers package. If all you need is to store exact numbers like "1 + √3", you may want to use Data.Number.CReal instead of symbolic arithmetics. It stores the expressions and can be computed to arbitrary number of digits when needed.

Prelude Data.Number.CReal> let cx = 1 + sqrt (3 :: CReal)
Prelude Data.Number.CReal> showCReal 400 cx 
"2.7320508075688772935274463415058723669428052538103806280558069794519330169088000370811461867572485756756261414154067030299699450949989524788116555120943736485280932319023055820679748201010846749232650153123432669033228866506722546689218379712270471316603678615880190499865373798593894676503475065760507566183481296061009476021871903250831458295239598329977898245082887144638329173472241639845878553977"

There is also a Data.Number.Symbolic module in the package but the description says "It's mainly useful for debugging".

Kreiker

CReal won't give you equality though, right? So I'd think that's a no-go. – Taryn

@sclv: It implements CReal, except that it may take infinitely long if done correctly. CReal's == terminates after 40 digits. – Kreiker

"Note that the comparison operations on CReal may diverge since it is (by necessity) impossible to implementent them correctly and always terminating." That rules out CReal for me. I need to avoid conversion to real numbers in order to hash these values. – Opiate

Answer 2

It seems you are looking for Computer Algebra System (CAS) in Haskell. Inspite of so many references to algebraic objects in the names of Haskell packages/modules, I've never heard of a general purpose and well-maintained CA system in Haskell (like SymPy or Sage in Python).

However in the list of Computer Algebra Systems on Wikipedia I've found a reference to

DoCon. The Algebraic Domain Constructor

It uses a non-standard license, but I dare say it is still Open Source (though with rename and attribution requirements). As of July 2010 docon-2.11 still builds with GHC 6.12.1 and runs demos/tests (I only had to insert a LANGUAGE FlexibleContexts pragma in one file of the demo).

DoCon is well documented (362 pages of the Manual). Its Manual is packed inside of the zip with sources, so I put it online separately for convenience:

DoCon 2.11 Manual.ps

Please look through to check if it suits your needs.

Schwenk

DoCon seems a bit heavyweight for the poster's purpose. – Taryn

I agree, but I don't know about anything else for Haskell. – Schwenk

DoCon looks pretty formidable. All I really need is a Haskell implementation of Landau's algorithm for denesting radicals (and something to do basic arithmetic with rationals and square roots and so on). – Opiate

Link to DoCon on haskell.org seems to be dead and the latest version of it seems to be on ftp.botik.ru/pub/local/Mechveliani/docon/2.11 – Forefront

Do you know what kind of features DoCon supports? – Keefe

Answer 3

Check out the cyclotomic package, which implements exact arithmetic on the cyclotomic numbers. These include all algebraic numbers (hence in particular 1+sqrt(3)) and the key operations (like equality) are decidable.

They do not provide an Ord instance (for the same reason the complex numbers do not), but one can implement a non-semantic instance if all one needs is to use them as keys in a lookup table. You may want to contact the author about how to do this correctly, as there may be some invariants that are not obvious (e.g. one may need to be careful about zeros in the coeffs map).

Sarcoid