August 2018 - Haskell-Cafe

Working around floating-point inaccuracies
by Michail Pevnev 07 Aug '18

07 Aug '18

Hello everyone! For a library I write at the moment, I made a class for approximate geometric equality comparisons (and dubbed it `ApproxEq`). It's not a very lawful class, but there is one invariant that should hold absolutely always - if two entities coincide but have different representations, they should compare "equal". All instances for my geometric entities seem to uphold this invariant (btw, QuickCheck is awesome). Except for the `Plane` type, which gives me a false negative once in about 50000 runs. I've chosen to represent planes by two vectors: an arbitrary point on a plane, and a normal. To test this invariant I translate the plane by a vector parallel to the plane, and then compare the translated plane with the original. The general pattern to these failures is that one of the coordinates of the origin point of the untranslated plane is huge compared to the other two - by 4-6 orders of magnitude, while the translation vector is not particularly big and has about the same magnitude as the two smaller coordinates. I suspect that this difference throws off the function that tests if a point belongs to a plane (which is in turn used in the equality comparison) by filling lower digits of participating numbers with floating-point garbage. I can live with this false negative, but I'd prefer not to. There probably is a clever way to work around it, I just can't find it. Any ideas? Thanks in advance. The relevant code is below. ``` -- | A plane is represented by an arbitrary point on it and a normal vector. data Plane a = Plane (V3 a) (V3 a) deriving (Show) instance (Epsilon a, Floating a) => ApproxEq (Plane a) where p1@(Plane o1 n1) ~== p2@(Plane o2 n2) = res where n1' = normalize n1 n2' = normalize n2 parallel = n1' ~== n2' antiparallel = (-n1') ~== n2' originsAreTheSame = o1 ~== o2 originsBelong = pointOnPlane p1 o2 || pointOnPlane p2 o1 res = (parallel || antiparallel) && (originsAreTheSame || originsBelong) -- | Return True if a point lies on a plane. pointOnPlane :: (Epsilon a, Floating a) => Plane a -> V3 a -> Bool pointOnPlane (Plane o n) v = nearZero $ delta `dot` n' where delta = normalize $ o - v n' = normalize n ``` -- Michail.

3 3

How to increase solver iterations?
by David Banas 06 Aug '18

06 Aug '18

Hi all, I’m getting this ghc compilation error: solveSimpleWanteds: too many iterations (limit = 4) Set limit with -fsolver-iterations=n; n=0 for no limit These are the only plug-ins I’m using: {-# OPTIONS_GHC -fplugin GHC.TypeLits.KnownNat.Solver #-} {-# OPTIONS_GHC -fplugin TypeNatSolver #-} I’ve tried the following, one at a time: {-# OPTIONS_GHC -fplugin-opt=TypeNatSolver:solver-iterations=10 #-} {-# OPTIONS_GHC -fplugin-opt=TypeNatSolver:fsolver-iterations=10 #-} {-# OPTIONS_GHC -fplugin-opt=GHC.TypeLits.KnownNat.Solver:solver-iterations=10 #-} {-# OPTIONS_GHC -fplugin-opt=GHC.TypeLits.KnownNat.Solver:fsolver-iterations=10 #-} But, I always get, “(limit = 4)”. Does anyone know how to change the number of solver iterations? Thanks, -db

2 4

Bizarre GHC error.
by David Banas 05 Aug '18

05 Aug '18

Has anyone seen this kind of error from GHC? dca9047d694f:concat-learn a594349$ stack build :lenna concat-learn-0.2.0.0: build (lib + exe) Preprocessing library concat-learn-0.2.0.0... [6 of 6] Compiling ConCat.Learn.CNN.Conv ( src/ConCat/Learn/CNN/Conv.hs, .stack-work/dist/x86_64-osx/Cabal-1.24.2.0/build/ConCat/Learn/CNN/Conv.o ) user error (Unexpected result from the SMT solver: Expected: success Result: (error "line 1515 column 22: unknown constant tn_1" ) ) -- While building custom Setup.hs for package concat-learn-0.2.0.0 using: /Users/a594349/.stack/setup-exe-cache/x86_64-osx/Cabal-simple_mPHDZzAJ_1.24.2.0_ghc-8.0.2 --builddir=.stack-work/dist/x86_64-osx/Cabal-1.24.2.0 build lib:concat-learn exe:lenna --ghc-options " -ddump-hi -ddump-to-file" Process exited with code: ExitFailure 1 I started seeing it when I started trying to use the someNatVal function.

2 1

Re: [Haskell-cafe] Working around floating-point inaccuracies
by Olaf Klinke 05 Aug '18

05 Aug '18

Michail, Each plane in 3d space is determined by a single linear equation with 3 unknowns. Essentially the equation is what pointOnPlane evaluates. Two planes are equal if the system of linear equations consisting of both equations has rank 1. This is a standard concept of linear algebra, hence the answer to your problem (and code for a good implementation) should be found in the literature on that subject - numerical linear algebra. Google "numerical rank of a matrix". The concepts you are looking for is the "condition number" or "operator norm". You could try to enforce an invariant that the representation is always as nice as possible, numerically. If you are okay with a vector space over the rational numbers, you could represent your planes by an equation with integer coefficients, which makes equality testing independent of floating point issues. Olaf

1 0

Fixity of ($) and (.) vs. (&) and (>>>)
by Frederik Hanghøj Iversen 05 Aug '18

05 Aug '18

With function composition I can easily write something like h . g . f $ expr However if I want to write the equivalent in left-to-right composition style: expr & f >>> g >>> h This is not possible due to a parsing error arising from the fixity of the operators. (>>>) is provided by Control.Arrow and (&) by Data.Function. My question is, would it not be better to *decrement* the fixity of (&) by one or *increment* the fixity of (>>>) by one (probably rather the latter)? -- Regards *Frederik Hanghøj Iversen*

2 1

ANN: lsp-test-0.1.0.0
by Luke Lau 04 Aug '18

04 Aug '18

My GSoC 2018 project (and first package!), lsp-test <https://hackage.haskell.org/package/lsp-test-0.1.0.0>, is now available on Hackage. It allows you to carry out functional end-to-end tests at a high level for LSP <https://microsoft.github.io/language-server-protocol/> servers, and we’re currently using it in haskell-ide-engine <https://github.com/haskell/haskell-ide-engine>. Many thanks to Alan Zimmerman and Zubin Duggal for their invaluable help this summer. Hopefully it will help improve your LSP servers, or maybe entice you to make one for your language!

1 0

Re: [Haskell-cafe] [random-fu] sampleRVar with StdGen in RWS?
by dominic＠steinitz.org 04 Aug '18

04 Aug '18

> > I suppose you could write an orphan instance for RWST if you really > > wanted to. > > That's what I'll most probably do for my small project, but I was > wondering whether it made sense to make a pull request to random-fu. To > me, having a MonadRandom for both StateT and RWST seems very natural. Please do make a PR - I will accept it immediately :) Dominic Steinitz dominic(a)steinitz.org http://idontgetoutmuch.wordpress.com Twitter: @idontgetoutmuch

2 1

A Performance Puzzle
by Gregory Wright 04 Aug '18

04 Aug '18

Hi, Something Haskell has lacked for a long time is a good medium-duty linear system solver based on the LU decomposition. There are bindings to the usual C/Fortran libraries, but not one in pure Haskell. (An example "LU factorization" routine that does not do partial pivoting has been around for years, but lacking pivoting it can fail unexpectedly on well-conditioned inputs. Another Haskell LU decomposition using partial pivoting is around, but it uses an inefficient representation of the pivot matrix, so it's not suited to solving systems of more than 100 x 100, say.) By medium duty I mean a linear system solver that can handle systems of (1000s) x (1000s) and uses Crout's efficient in-place algorithm. In short, a program does everything short of exploiting SIMD vector instructions for solving small subproblems. Instead of complaining about this, I have written a little library that implements this. It contains an LU factorization function and an LU system solver. The LU factorization also returns the parity of the pivots ( = (-1)^(number of row swaps) ) so it can be used to calculate determinants. I used Gustavson's recursive (imperative) version of Crout's method. The implementation is quite simple and deserves to be better known by people using functional languages to do numeric work. The library can be downloaded from GitHub: https://github.com/gwright83/luSolve The performance scales as expected (as n^3, a linear system 10 times larger in each dimension takes a 1000 times longer to solve): Benchmark luSolve-bench: RUNNING... benchmarking LUSolve/luFactor 100 x 100 matrix time 1.944 ms (1.920 ms .. 1.980 ms) 0.996 R² (0.994 R² .. 0.998 R²) mean 1.981 ms (1.958 ms .. 2.009 ms) std dev 85.64 μs (70.21 μs .. 107.7 μs) variance introduced by outliers: 30% (moderately inflated) benchmarking LUSolve/luFactor 500 x 500 matrix time 204.3 ms (198.1 ms .. 208.2 ms) 1.000 R² (0.999 R² .. 1.000 R²) mean 203.3 ms (201.2 ms .. 206.2 ms) std dev 3.619 ms (2.307 ms .. 6.231 ms) variance introduced by outliers: 14% (moderately inflated) benchmarking LUSolve/luFactor 1000 x 1000 matrix time 1.940 s (1.685 s .. 2.139 s) 0.998 R² (0.993 R² .. 1.000 R²) mean 1.826 s (1.696 s .. 1.880 s) std dev 93.63 ms (5.802 ms .. 117.8 ms) variance introduced by outliers: 19% (moderately inflated) Benchmark luSolve-bench: FINISH The puzzle is why the overall performance is so poor. When I solve random 1000 x 1000 systems using the linsys.c example file from the Recursive LAPACK (ReLAPACK) library -- which implements the same algorithm -- the average time is only 26 ms. (I have tweaked ReLAPACK's dgetrf.c so that it doesn't use optimized routines for small matrices. As near as I can make it, the C and haskell versions should be doing the same thing.) The haskell version runs 75 times slower. This is the puzzle. My haskell version uses a mutable, matrix of unboxed doubles (from Kai Zhang's matrices <https://hackage.haskell.org/package/matrices> library). Matrix reads and writes are unsafe, so there is no overhead from bounds checking. Let's look at the result of profiling: Tue Jul 31 21:07 2018 Time and Allocation Profiling Report (Final) luSolve-hspec +RTS -N -p -RTS total time = 7665.31 secs (7665309 ticks @ 1000 us, 1 processor) total alloc = 10,343,030,811,040 bytes (excludes profiling overheads) COST CENTRE MODULE SRC %time %alloc unsafeWrite Data.Matrix.Dense.Generic.Mutable src/Data/Matrix/Dense/Generic/Mutable.hs:(38,5)-(39,38) 17.7 29.4 basicUnsafeWrite Data.Vector.Primitive.Mutable Data/Vector/Primitive/Mutable.hs:115:3-69 14.7 13.0 unsafeRead Data.Matrix.Dense.Generic.Mutable src/Data/Matrix/Dense/Generic/Mutable.hs:(34,5)-(35,38) 14.2 20.7 matrixMultiply.\.\.\ Numeric.LinearAlgebra.LUSolve src/Numeric/LinearAlgebra/LUSolve.hs:(245,54)-(249,86) 13.4 13.5 readByteArray# Data.Primitive.Types Data/Primitive/Types.hs:184:30-132 9.0 15.5 basicUnsafeRead Data.Vector.Primitive.Mutable Data/Vector/Primitive/Mutable.hs:112:3-63 8.8 0.1 triangularSolve.\.\.\ Numeric.LinearAlgebra.LUSolve src/Numeric/LinearAlgebra/LUSolve.hs:(382,45)-(386,58) 5.2 4.5 matrixMultiply.\.\ Numeric.LinearAlgebra.LUSolve src/Numeric/LinearAlgebra/LUSolve.hs:(244,54)-(249,86) 4.1 0.3 primitive Control.Monad.Primitive Control/Monad/Primitive.hs:152:3-16 3.8 0.0 basicUnsafeRead Data.Vector.Unboxed.Base Data/Vector/Unboxed/Base.hs:278:813-868 3.3 0.0 basicUnsafeWrite Data.Vector.Unboxed.Base Data/Vector/Unboxed/Base.hs:278:872-933 1.5 0.0 triangularSolve.\.\ Numeric.LinearAlgebra.LUSolve src/Numeric/LinearAlgebra/LUSolve.hs:(376,33)-(386,58) 1.3 0.1 <snip> A large amount of time is spent on the invocations of unsafeRead and unsafeWrite. This is a bit suspicious -- it looks as if these call may not be inlined. In the Data.Vector.Unboxed.Mutable library, which provides the underlying linear vector of storage locations, the unsafeRead and unsafeWrite functions are declared INLINE. Could this be a failure of the 'matrices' library to mark its unsafeRead/Write functions as INLINE or SPECIALIZABLE as well? On the other hand, looking at the core (.dump-simpl) of the library doesn't show any dictionary passing, and the access to matrix seem to be through GHC.Prim.writeDoubleArray# and GHC.Prim.readDoubleArray#. If this program took three to five times longer, I would not be concerned, but a factor of seventy five indicates that I've missed something important. Can anyone tell me what it is? Best Wishes, Greg

4 6

Re: [Haskell-cafe] A Performance Puzzle
by dominic＠steinitz.org 04 Aug '18

04 Aug '18

> Something Haskell has lacked for a long time is a good medium-duty > linear system solver based on the LU decomposition. There are bindings > to the usual C/Fortran libraries, but not one in pure Haskell. (An > example "LU factorization" routine that does not do partial pivoting has > been around for years, but lacking pivoting it can fail unexpectedly on > well-conditioned inputs. Another Haskell LU decomposition using partial > pivoting is around, but it uses an inefficient representation of the > pivot matrix, so it's not suited to solving systems of more than 100 x > 100, say.) > > By medium duty I mean a linear system solver that can handle systems of > (1000s) x (1000s) and uses Crout's efficient in-place algorithm. In > short, a program does everything short of exploiting SIMD vector > instructions for solving small subproblems. > > Instead of complaining about this, I have written a little library that > implements this. It contains an LU factorization function and an LU > system solver. The LU factorization also returns the parity of the > pivots ( = (-1)^(number of row swaps) ) so it can be used to calculate > determinants. I used Gustavson's recursive (imperative) version of > Crout's method. The implementation is quite simple and deserves to be > better known by people using functional languages to do numeric work. > The library can be downloaded from GitHub: > https://github.com/gwright83/luSolve <https://github.com/gwright83/luSolve> Great news :) Dominic Steinitz dominic(a)steinitz.org http://idontgetoutmuch.wordpress.com Twitter: @idontgetoutmuch

1 1

Need some help figuring out how to use the repl with reflex using only stack
by Michael Litchard 03 Aug '18

03 Aug '18

I've created a minimal example to show you what I've tried. Below is also a truncated error log. Could someone help me figure out how to get ghci working with this example? https://github.com/mlitchard/reflex-todo stack repl --stack-yaml=stack-ghc.yaml Truncated error log Error: -- While building custom Setup.hs for package jsaddle-dom-0.9.2.0 using: /home/mlitchard/.stack/setup-exe-cache/x86_64-linux/Cabal-simple_mPHDZzAJ_1.24.2.0_ghc-8.0.2 --builddir=.stack-work/dist/x86_64-linux/Cabal-1.24.2.0 build lib:jsaddle-dom --ghc-options " -ddump-hi -ddump-to-file" Process exited with code: ExitFailure 1 Logs have been written to: /home/mlitchard/projects/git/reflex-todo/.stack-work/logs/jsaddle-dom-0.9.2.0.log Preprocessing library jsaddle-dom-0.9.2.0... [587 of 599] Compiling JSDOM.Custom.XMLHttpRequest ( src/JSDOM/Custom/XMLHttpRequest.hs, .stack-work/dist/x86_64-linux/Cabal-1.24.2.0/build/JSDOM/Custom/XMLHttpRequest.o ) /home/mlitchard/projects/git/reflex-todo/.stack-work/downloaded/Vheiln5kqwE0/src/JSDOM/Custom/XMLHttpRequest.hs:39:46: error: • Could not deduce (Control.Monad.Catch.MonadThrow Language.Javascript.JSaddle.Types.JSM) arising from a use of ‘throwM’ from the context: MonadDOM m bound by the type signature for: throwXHRError :: MonadDOM m => Maybe XHRError -> m () at src/JSDOM/Custom/XMLHttpRequest.hs:38:1-53 • In the second argument of ‘(.)’, namely ‘throwM’ In the second argument of ‘maybe’, namely ‘(liftDOM . throwM)’ In the expression: maybe (return ()) (liftDOM . throwM) /home/mlitchard/projects/git/reflex-todo/.stack-work/downloaded/Vheiln5kqwE0/src/JSDOM/Custom/XMLHttpRequest.hs:42:20: error: • No instance for (Control.Monad.Catch.MonadMask Language.Javascript.JSaddle.Types.JSM) arising from a use of ‘bracket’ • In the first argument of ‘(.)’, namely ‘bracket aquire id’ In the expression: bracket aquire id . const In an equation for ‘withEvent’: withEvent aquire = bracket aquire id . const /home/mlitchard/projects/git/reflex-todo/.stack-work/downloaded/Vheiln5kqwE0/src/JSDOM/Custom/XMLHttpRequest.hs:45:31: error: • Could not deduce (Control.Monad.Catch.MonadCatch Language.Javascript.JSaddle.Types.JSM) arising from an operator section from the context: MonadDOM m bound by the type signature for: send' :: MonadDOM m => XMLHttpRequest -> Maybe JSVal -> m () at src/JSDOM/Custom/XMLHttpRequest.hs:44:1-62 • In the expression: (`onException` abort self) In the second argument of ‘($)’, namely ‘(`onException` abort self) $ do { result <- liftIO newEmptyMVar; r <- withEvent (onAsync self Generated.error . liftIO $ putMVar result (Just XHRError)) $ withEvent (onAsync self abortEvent . liftIO $ putMVar result (Just XHRAborted)) $ withEvent (onAsync self load . liftIO $ putMVar result Nothing) $ do { void $ case mbVal of { Nothing -> ... Just val -> ... }; liftIO $ takeMVar result }; throwXHRError r }’ In the expression: liftDOM $ (`onException` abort self) $ do { result <- liftIO newEmptyMVar; r <- withEvent (onAsync self Generated.error . liftIO $ putMVar result (Just XHRError)) $ withEvent (onAsync self abortEvent . liftIO $ putMVar result (Just XHRAborted)) $ withEvent (onAsync self load . liftIO $ putMVar result Nothing) $ do { void $ case mbVal of { Nothing -> ... Just val -> ... }; liftIO $ takeMVar result }; throwXHRError r }

4 4