News aggregator

Ken T Takusagawa: [kdrtkgdr] Polymorphic matrix inversion

Planet Haskell - Mon, 05/18/2015 - 1:44am

Here is matrix inversion implemented in pure Haskell and a demonstration of its use with Complex Rational exact arithmetic:

A= [ 9 8*i 9*i 4 8*i 3 5*i 3*i ; 6*i 6 7*i 5 0 3*i 5*i 7 ; 4 4*i 4*i 8 1*i 3 1 9*i ; 4 6*i 7 5 4*i 7 4 4 ; 0 3 6 0 4 2*i 0 7 ; 7 2 0 4*i 3 3*i 1 4*i ; 4*i 3 8 1 2*i 3 1 3*i ; 3 3 4*i 3*i 6 3 7 1*i ]

Ainv= [ -651341+282669*i 70449+105643*i 470260+543736*i -90558-322394*i 940582+401976*i -1471210-32706*i 304731+202312*i 428573+497242*i ; 544367-80697*i -1154274+187794*i 1139302-87593*i -21921+1224087*i 1488234-1168263*i -1627965+1312344*i -1248400-535541*i 337176-362289*i ; -31970+991102*i 93690-139399*i 123282-341373*i -421343-757909*i 50198+495419*i 8593-654052*i -468577+527063*i 897227+455914*i ; 695254+159129*i -629809+1226054*i -2027820-1557744*i -161289+1062653*i -1299979-787107*i 915864+11456*i 1378121-78438*i 1043558-421873*i ; -925872-186803*i 1371020-146791*i -2291428-34310*i 2099076-57282*i -3405480+2662395*i 1616586-1020331*i 313380-265939*i -1386116-96576*i ; -1420678-1211999*i 1206717-844239*i 93772+1350941*i 1290846-32987*i -511+2133602*i 1126031+1379618*i -2659652-75501*i -2000675-207615*i ; 2039672+316590*i -813732+665441*i 417543-103784*i -2312041+106452*i 1746852-2305394*i -871774-685499*i 1641748-24893*i -261188+84637*i ; -23113-302279*i -610268-221894*i 1101428+322959*i -838351-211053*i -239412-540356*i 160747+259506*i 736020+689615*i -180808+391291*i ] / (-14799118+6333791*i)

Aesthetically striking is how simple input matrices become complicated when inverted: complexity seemingly appears out of nowhere.  The complexity arises from a convolution of several effects: numerators and denominators intermingle as fractions get added; real and imaginary parts intermingle as complex numbers get multiplied; matrix elements intermingle in row operations.

(Perhaps this mixing could be put to cryptographic use someday? Row operations do vaguely look like Salsa20. AES has a field inversion to define its S box.)

The code is kind of a mess, not really trying to achieve performance: we compute the LU decomposition to get the determinant, which is used just to provide the scalar factor in the final displayed result of the inverse to avoid fractions inside the matrix.  (It is neat that multiplying through by the determinant makes fractions disappear.)  We do a separately implemented Gauss-Jordan elimination on the original matrix to compute the inverse, then multiply by the determinant computed via LU.

We made modifications to two library packages.

We forked the base module Data.Complex to a new module Data.ComplexNum to provide a Complex type that does not require RealFloat (so only requires Num).  (Complex normally requires RealFloat because abs and signum of a Complex number requires sqrt.)  Avoiding RealFloat allowed us to form Complex Rational, i.e., Complex (Ratio Integer), a powerful data type.  We defined abs and signum as error.

Our starting point for matrix operations was Data.Matrix in the matrix package (by Daniel Díaz).  The original luDecomp function calls abs to select the largest pivot during LU decomposition.  The output type of abs is constrained in the Num class to be the same as the input type (abs :: a -> a), so Complex numbers weirdly provide a Complex output type for abs even through mathematically the absolute value of a complex number is real.  Unfortunately Complex numbers do not provide Ord, so we cannot select the "largest" absolute value as the pivot.  Therefore, we added a new entry point to LU decomposition, luDecompWithMag, to allow passing in a custom function to compute the magnitude.  Since we are avoiding square root, we provided magnitude-squared (magnitude2) as the pivot-choosing function.

We fixed some (but not all) space leaks in LU decomposition so processing matrices of size 100x100 no longer requires gigabytes of memory.

We added to Data.Matrix two different implementations of matrix inversion both which use monadic imperative style for in-place modification of the augmented matrix with row operations: one (invertS) uses Control.Monad.Trans.State.Strict and the other (invert) uses MVector and Control.Monad.ST.  The latter is a little bit faster. Both implementations required care to avoid space leaks, which were tracked down using ghc heap profiling.

The modifications to Data.Matrix can be tracked in this github repository.

Runtime (in seconds) and maxresident memory usage (k) of inversion of random Complex Rational matrices, where each entry in the original matrix is a random single-digit pure real or pure imaginary number (as in the example above with size 8), of sizes 10 through 320: [ 10 0.01 2888 ; 20 0.26 4280 ; 30 1.40 5324 ; 40 4.84 7132 ; 50 12.32 10204 ; 60 27.05 14292 ; 70 52.67 19416 ; 80 94.36 26588 ; 90 157.18 33752 ; 100 250.12 44000 ; 110 373.71 56524 ; 120 546.32 69600 ; 130 768.92 85988 ; 140 1056.05 103632 ; 150 1419.47 124900 ; 160 1877.97 148696 ; 170 2448.16 176364 ; 180 3130.31 208104 ; 190 3963.96 238824 ; 200 4958.93 277504 ; 210 6138.61 318704 ; 220 7543.16 364544 ; 230 9252.55 413700 ; 240 11115.32 467196 ; 250 13217.16 524300 ; 260 15690.80 594956 ; 270 18520.73 658448 ; 280 21761.36 734460 ; 290 25509.77 812288 ; 300 30048.34 1022028 ; 310 34641.25 1218636 ; 320 39985.63 1419340 ]

Runtime and memory for Hilbert matrices (Rational) of sizes 10 through 510: [ 10 0.00 2736 ; 20 0.03 3676 ; 30 0.14 4164 ; 40 0.51 4608 ; 50 1.45 5804 ; 60 3.65 8196 ; 70 7.86 9224 ; 80 15.59 11096 ; 90 27.85 13444 ; 100 45.03 17320 ; 110 67.97 21408 ; 120 98.61 26876 ; 130 137.02 27132 ; 140 187.48 29664 ; 150 248.99 37792 ; 160 325.17 38816 ; 170 420.00 43920 ; 180 529.02 55796 ; 190 659.03 56304 ; 200 811.39 65520 ; 210 980.33 70912 ; 220 1202.42 72608 ; 230 1426.34 82852 ; 240 1696.02 89996 ; 250 2014.39 97192 ; 260 2300.64 109496 ; 270 2693.48 118692 ; 280 3124.52 130980 ; 290 3589.06 138164 ; 300 4158.67 210900 ; 310 4711.61 223188 ; 320 5323.13 243692 ; 330 6047.59 262104 ; 340 6789.74 241640 ; 350 7621.69 269268 ; 360 8433.56 338924 ; 370 9447.28 360428 ; 380 10496.28 358356 ; 390 11662.98 422872 ; 400 12935.35 375772 ; 410 14203.69 477164 ; 420 15655.88 420840 ; 430 17143.12 547820 ; 440 19003.82 517104 ; 450 20592.28 550880 ; 460 22471.48 574428 ; 470 24484.14 604120 ; 480 26672.65 662492 ; 490 28958.52 766936 ; 500 31302.45 646132 ; 510 33932.76 731120 ]

Slope of runtime on a log-log plot is about 4.3.

According to Wikipedia, the worst case run time (bit complexity) of Gaussian elimination is exponential, but the Bareiss algorithm can guarantee O(n^5): Bareiss, Erwin H. (1968), "Sylvester's Identity and multistep integer-preserving Gaussian elimination", Mathematics of Computation 22 (102): 565–578, doi:10.2307/2004533.  Future work: try the code presented here on the exponentially bad matrices described in the paper; implement Bareiss algorithm.

Also someday, it may be a fun exercise to create a data type encoding algebraic expressions which is an instance of Num, then use the polymorphism of the matrix code presented here to invert symbolic matrices.

Categories: Offsite Blogs

IsString [Char] instance

libraries list - Mon, 05/18/2015 - 1:08am
Greetings, Today, someone came into #haskell and asked why they couldn't type the equivalent of: > "hi" ++ "bye" into GHCi with OverloadedStrings enabled. The answer is that it's ambiguous, because (++) only determines the strings to be [a], and not [Char]. I noticed that this could actually be solved by making the instance: instance (a ~ Char) => IsString [a] where ... Which causes [Char] to be inferred as soon as [a] is. I then searched my libraries mail and noticed that we'd discussed this two years ago. The proposal for this instance change was rejected based on ExtendedDefaultRules being beefed up to solve this case. But then no one actually implemented the better defaulting. So, I'm proposing that the issue be fixed for real. I'm not terribly concerned with how it gets fixed, but there's not a great reason for this to not behave better than it currently does. If someone steps up and makes defaulting better, than that's great. But if not, then the libraries committee can fix this very eas
Categories: Offsite Discussion

CFP - Information and Computation special issue on Implicit Computational Complexity

General haskell list - Sun, 05/17/2015 - 11:55pm
====================================================================== Call for Papers INFORMATION & COMPUTATION Special Issue on Implicit Computational Complexity (open post-conference publication of the workshops DICE 2014 and DICE 2015) Deadline: July 1st 2015 Guest Editors: Marco Gaboardi <m.gaboardi< at >dundee.ac.uk> Ulrich Schöpp <schoepp< at >tcs.ifi.lmu.de> ====================================================================== The area of Implicit Computational Complexity has grown from several proposals for using logic and formal methods to provide languages for complexity-bounded computation (such as polynomial time, polynomial space or logarithmic space computation). Its aim is to study computational complexity without reference to external measuring conditions or particular machine models, but only in terms of language restrictions or logical/computational principles implying complexity properties. We welcome contributions on various aspects of Implicit Computational Com
Categories: Incoming News

Call for participation: 8th International School on Rewriting - ISR 2015

General haskell list - Sun, 05/17/2015 - 7:52pm
Call for participation 8th International School on Rewriting - ISR 2015 August 10-14, Leipzig, Germany http://www.imn.htwk-leipzig.de/ISR2015/ * early registration deadline: July 1 * student research posters welcome ===================================================================== The 8th International School on Rewriting (ISR 2015) is aimed at master and PhD students, researchers, and practitioners interested in the study of rewriting concepts and their applications. The school features lectures by renowned researchers in rewriting, and is organized in two parallel tracks: Basic: aimed at students that enter the field. Aart Middeldorp and Sarah Winkler: Introductory Course Advanced: several shorter courses, showing different areas of rewriting research, with applications. David Sabel and Manfred Schmidt-Schauß: Rewriting Techniques for Correctness of Program Transformations Makoto Hamana: Algebraic Semantics of Higher-Order Abstract Syntax and Second-Order Rewriting
Categories: Incoming News

FIXME pragma

haskell-cafe - Sun, 05/17/2015 - 5:42pm
What's the feeling on having a FIXME pragma so that I can attach warnings to unfinished things? {-# FIXME foo "Reasons here." #-} I would use the WARNING pragma but that doesn't work within a module and only triggers on use. Compiler errors are the one thing I and everyone else pays attention to, it would be very handy to have more control over things GHC reports to the developer to aid development. Ciao _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Draining the Swamp: Micro Virtual Machines as Solid Foundation for Language Development

Lambda the Ultimate - Sun, 05/17/2015 - 3:46pm

Draining the Swamp: Micro Virtual Machines as Solid Foundation for Language Development
Kunshan Wang, Yi Lin, Stephen Blackburn, Michael Norrish, Antony Hosking
2015

Many of today's programming languages are broken. Poor performance, lack of features and hard-to-reason-about semantics can cost dearly in software maintenance and inefficient execution. The problem is only getting worse with programming languages proliferating and hardware becoming more complicated. An important reason for this brokenness is that much of language design is implementation-driven. The difficulties in implementation and insufficient understanding of concepts bake bad designs into the language itself. Concurrency, architectural details and garbage collection are three fundamental concerns that contribute much to the complexities of implementing managed languages. We propose the micro virtual machine, a thin abstraction designed specifically to relieve implementers of managed languages of the most fundamental implementation challenges that currently impede good design. The micro virtual machine targets abstractions over memory (garbage collection), architecture (compiler backend), and concurrency. We motivate the micro virtual machine and give an account of the design and initial experience of a concrete instance, which we call Mu, built over a two year period. Our goal is to remove an important barrier to performant and semantically sound managed language design and implementation. Inside you will find the specification of an LLVM-inspired virtual instruction set with a memory model (enables proper GC support) including a specification of concurrent weak-memory operations (reusing C(++)11, a debatable choice), relatively rich control-flow primitive (complete stack capture enabling coroutines or JIT-style de-optimization), and live code update.
Categories: Offsite Discussion

Eric Kidd: Unscientific column store benchmarking in Rust

Planet Haskell - Sun, 05/17/2015 - 2:03pm

I've been fooling around with some natural language data from OPUS, the “open parallel corpus.” This contains many gigabytes of movie subtitles, UN documents and other text, much of it tagged by part-of-speech and aligned across multiple languages. In total, there's over 50 GB of data, compressed.

“50 GB, compressed” is an awkward quantity of data:

Let's look at various ways to tackle this.

Read more…

Categories: Offsite Blogs

Announcement: Gipeda, the git performance dashboard

haskell-cafe - Sun, 05/17/2015 - 1:46pm
Dear Haskellers, a while ago, I set up a performance dashboard¹ for GHC, based on codespeed², but I was dissatisfied, so in the end, I wrote a new one, called Gipeda for “Git Performance Dashboard”. The git in the name as, in contrast to codespeed, I do not try to be VCS-agnostic but do want to use and expose the structure of your project’s git repository in the output. You can have a look at http://perf.haskell.org/ghc. It should be relatively self-explanatory. Just note that by default it hides boring stuff (commits and results with no significant change), you can select what to show in the top-right corner. The idea behind gipeda is relatively simple. Starting with a directory with one file for each of your project’s benchmarked commit, gipeda digests this to produce a bunch of JSON files. It uses shake³ to avoid unnecessary recalculations. A static HTML file with lots o
Categories: Offsite Discussion

Escaping Cabal Hell with NixOS

Haskell on Reddit - Sun, 05/17/2015 - 1:24pm

I love writing Haskell, but until recently I was totally discouraged by Cabal hell. I've just lived through it too many times. I know about sandboxes, and I've used them with some success, but rebuilding all the dependencies everytime I need to create a new project was a total bummer.

So it was with some excitement that I read ocharles's post about using nix as a cabal cache. I'm happy to report that nix has liberated me from the dread that I felt everytime I wanted to start something new using Haskell. Its great, and after the first invocation of nix-shell, its super fast. I'm back to loving Haskell again!

The thing that was holding me back from trying it is that I was daunted by the nixos install process. I know you can use nix without nixos, but I wanted the full experience. I've lived through slackware, debian, ubuntu and probably a couple distros I don't even remember. But its been a long time since I got wireless drivers working from a cold install with no network connection. Its a pain every time. Using nothing but google and my wits, I concocted the following invocation which got my WIFI up and running:

nmcli dev wifi connect HOTSPOT password PASSWORD iface wlp3s0

and suddenly I had a working machine, and the fresh clean feeling of a brand new distribution, with package dependencies specified declaratively. It feels great.

If you also want to try doing webstuff with Haskell, Yesod and Nix, check out the nix-shell settings I'm using. (I stole most of it from somewhere I can't remember, but I'll update with attribution if I can recall)

submitted by ludflu
[link] [22 comments]
Categories: Incoming News

ARM64 Haskell via GHC 7.10.1 - How to build?

Haskell on Reddit - Sun, 05/17/2015 - 11:51am

(Cross-posted from the Haskell-iPhone mailing list, which I suspect might be dead)

I see from the discussion in GHC Trac #7942 that ARM64 support has been merged into GHC and should be available in 7.10.1. This is wonderful — and necessary for iOS development if one intends to pass through the Apple App Store, as since February new apps are rejected lest they support ARM64.

However, while scripts seem to be provided in ghc-ios-scripts for installing binaries of GHC 7.8.3 for the iOS Simulator (i386-apple-darwin11) and actual iOS devices (arm-apple-darwin10, 32-bit ARM), the scripts for aarch64-apple-darwin14 (ARM64 on iOS devices) aren’t used by the main wrapper scripts and the installation scripts don’t appear to mention anything about installing a GHC built for ARM64 cross-compiling — indeed, it’s only 32-bit ARM via GHC 7.8.3. I can’t find any binary GHCs on the 7.10.1 downloads either.

Following the guide for building a GHC cross-compiler for iOS targets, building GHC 7.10.1 for cross-compiling to ARM64 is currently failing for me (on a 2014 MacBook Air running Mac OS X Yosemite, 10.10.3) probably due to some trivial issue with my build environment. ./configure says:

checking version of gcc... configure: error: Need at least gcc version 3.0 (3.4+ recommended)

That’s configuring with

./configure --target=aarch64-apple-darwin14 --with-gcc=aarch64-apple-darwin14-clang

Furthermore,

$ gcc -v Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM version 6.1.0 (clang-602.0.49) (based on LLVM 3.6.0svn) Target: x86_64-apple-darwin14.3.0 Thread model: posix $ aarch64-apple-darwin14-clang aarch64-apple-darwin14-clang: line 7: /usr/local/opt/llvm/bin/clang: No such file or directory aarch64-apple-darwin14-clang: line 7: exec: /usr/local/opt/llvm/bin/clang: cannot execute: No such file or directory

Note the aarch64-apple-darwin14-clang command I’m running there is the script from ghc-ios-scripts, which seems overly simplistic compared to the same script for ARMv7 GHC-iOS.

I suppose the solution might even be as simple as installing an adequate version of LLVM+Clang over there at /usr/local/opt/llvm which the commands seem to be looking for — but which version might be appropriate? Moreover, is there some guide on how to install what needs to be installed? The ghc-ios scripts get 3.0, yet some Trac comments seem to suggest some very recent version of LLVM, possibly 3.6 or maybe just the latest development version.

Is this even something people have working?

Apologies if this isn’t the right forum for this — this is my first time on Reddit. Is there an iOS-specific subreddit? Or is this perhaps more appropriate for StackOverflow? I have no idea.

Edit: added link to GHC iOS cross compiling guide and details of build machine.

Update: I tried installing clang+llvm-3.6.0-x86_64-apple-darwin and pointing the arm-apple-darwin10-clang script at it. It then passes the configure command with this message buried somewhere in the middle of the log:

checking whether bootstrap compiler is affected by bug 9439... You are using a new version of LLVM that hasn't been tested yet! We will try though... opt: /var/folders/1w/gjgqw7hj6wlb4krcpxl0svhm0000gq/T/ghc489_0/ghc489_2.ll:7:6: error: unexpected type in metadata definition !0 = metadata !{metadata !"top", i8* null} ^ failed to compile

Running make thereafter:

[ 1 of 90] Compiling Distribution.Compat.CreatePipe ( libraries/Cabal/Cabal/Distribution/Compat/CreatePipe.hs, bootstrapping/Distribution/Compat/CreatePipe.o ) opt: /var/folders/1w/gjgqw7hj6wlb4krcpxl0svhm0000gq/T/ghc4275_0/ghc4275_40.ll:7:6: error: unexpected type in metadata definition !0 = metadata !{metadata !"top", i8* null} ^ make[1]: *** [utils/ghc-cabal/dist/build/tmp/ghc-cabal] Error 1 make: *** [all] Error 2

According to GHC bug comments, «GHC HEAD currently only supports LLVM version 3.6». I tried checking out the master branch to see if it’s something that had changed since the 7.10.1 release branch, but configuring and calling make after a checkout of master yields the same errors.

Update 2: Apparently the GHC I had installed won’t build with -fllvm if PATH picks LLVM 3.6. However, even after fixing PATH to get LLVM 3.5.2 and using GHC 7.10.1 to build, I get a new error:

/bin/sh: HaskellCPPCmd@: command not found make[1]: *** [compiler/stage1/build/primops.txt] Error 1

The file mk/config.mk says somewhere in the middle:

HS_CPP = @HaskellCPPCmd@ @HaskellCPPArgs@

which looks like something that should get substituted, but it seems to be taking the second @ as part of the name to substitute. Is this some preprocessor malfunctioning?

submitted by mgomezch
[link] [5 comments]
Categories: Incoming News

new to haskell, newish to programming, how do I tell cabal where to find a dependency I compiled from source?

Haskell on Reddit - Sun, 05/17/2015 - 11:23am

Hello, I compiled SDL2-2.0.3 in $HOME/local and would like to tell cabal to find it there when I cabal install helm.

I'm looking over the cabal documentation but the options seem to all regard where to put the installed package. Thanks for any help

submitted by sleepystudy
[link] [16 comments]
Categories: Incoming News

Generalizing Kleisli-composition to arrows

Haskell on Reddit - Sun, 05/17/2015 - 9:55am

Is there a way to generalize the >=> operator from (a -> m b) -> (b -> m c) -> (a -> m c) to p a (m b) -> p b (m c) -> p a (m c) for some Category/Arrow-subclass p?

I managed to do this for ArrowChoice and Maybe using pattern matching:

infixr 9 .? (.?) :: ArrowChoice p => p b (Maybe c) -> p a (Maybe b) -> p a (Maybe c) p1 .? p2 = proc a -> do mb <- p2 -< a case mb of Just b -> p1 -< b Nothing -> returnA -< Nothing

But can this be done with >>= instead of pattern matching, in order to define this function for arbitrary monads?

submitted by pwhiddlestone
[link] [9 comments]
Categories: Incoming News

no Web-Security component in Haskell?

haskell-cafe - Sun, 05/17/2015 - 7:11am
Hallo, I did not found anything comparable to Spring Security[1][2] (Java) or Symfony Security[3] (PHP) in Haskell. Both components are used in web applications to grant or deny access to resources based on roles, ACLs or custom voters. A naive strategy would be to port the concepts of both components, which are very similar, to Haskell. They represent a lot of accumulated knowledge from many experts about web security. Or are there better ways to do web security in a powerful language like Haskell? Regards, Thomas Koch [1] http://projects.spring.io/spring-security [2] http://docs.spring.io/autorepo/docs/spring-security/3.1.7.RELEASE/apidocs [3] http://api.symfony.com/master/Symfony/Component/Security/Core/SecurityContext.html
Categories: Offsite Discussion

Looking for an equivalent to blockly for functional languages?

Haskell on Reddit - Sun, 05/17/2015 - 6:45am

Is there a blockly for functional languages? If there isn't, what would it look like?

https://developers.google.com/blockly/

submitted by TTimo
[link] [7 comments]
Categories: Incoming News

help with hsqml-demo-samples

Haskell on Reddit - Sun, 05/17/2015 - 12:06am

I want to start developing with hsQML. I spent the whole afternoon installing QT5, cabal, hsqml and setting up the sandbox. My whole goal for today was to run the factorial sample.

I can't believe I'm asking this because I feel like it should be obvious, but how do I run this? A google search doesn't show more than a handful tutorials, in fact searching 'hsqml' in this subreddit will show them all in a very short list. I already built the sample in a sandbox. If I do something like:

ghc --make src/Factorial1.hs

I get this error:

Could not find module `Paths_hsqml_demo_samples'

Is the line import Paths_hsqml_demo_samples in Factorial1.hs some sort of placeholder?

submitted by OrangePhi
[link] [2 comments]
Categories: Incoming News

The Eventual Monad

Haskell on Reddit - Sat, 05/16/2015 - 4:35pm
Categories: Incoming News