September 2010 - Haskell-Cafe

ANNOUNCE: stringsearch 0.3.1, fast searching, splitting and replacing of ByteStrings
by Daniel Fischer 02 Sep '10

02 Sep '10

Changes vs. 0.3.0: - fixed a space leak in the splitting of lazy ByteStrings Changes of the 0.3 series vs. 0.2.*: - improved performance of the searching functions - new functionality: - breaking of ByteStrings at the first occurrence of a substring - splitting a ByteString at each occurrence of a substring - replacing all occurrences of a substring with another string Where bytestring provides the same functionality (Data.ByteString.breakSubstring, Data.ByteString.findSubstrings), the implementations in stringsearch are typically much faster. By default, stringsearch uses an enhanced Boyer-Moore algorithm to locate a pattern, but it also provides other algorithms which may be better in special cases (Knuth-Morris-Pratt; DFA).

1 0

Linking issues with HaskellDB/HDBC/ODBC
by Neil Davies 02 Sep '10

02 Sep '10

Hi Anyone got any hints as to why this linkage error is occurring (GHC 6.12.3, Mac OSX 10.6 (and 10.5 has same issue)): cabal install haskelldb-hdbc-odbc --enable-documentation --root-cmd=sudo --global Resolving dependencies... Configuring haskelldb-hdbc-odbc-0.13... Preprocessing library haskelldb-hdbc-odbc-0.13... Preprocessing executables for haskelldb-hdbc-odbc-0.13... Building haskelldb-hdbc-odbc-0.13... [1 of 1] Compiling Database.HaskellDB.HDBC.ODBC ( Database/HaskellDB/HDBC/ODBC.hs, dist/build/Database/HaskellDB/HDBC/ODBC.o ) Registering haskelldb-hdbc-odbc-0.13... [1 of 2] Compiling Database.HaskellDB.HDBC.ODBC ( Database/HaskellDB/HDBC/ODBC.hs, dist/build/DBDirect-hdbc-odbc/DBDirect-hdbc-odbc-tmp/Database/HaskellDB/HDBC/ODBC.o ) [2 of 2] Compiling Main ( DBDirect.hs, dist/build/DBDirect-hdbc-odbc/DBDirect-hdbc-odbc-tmp/Main.o ) Linking dist/build/DBDirect-hdbc-odbc/DBDirect-hdbc-odbc ... Undefined symbols: "_CFBundleCopyResourceURL", referenced from: _SQLDriverConnect_Internal in libodbc.a(connect.o) "___CFConstantStringClassReference", referenced from: cfstring=org.iodbc.core in libodbc.a(connect.o) cfstring=iODBCadm.bundle in libodbc.a(connect.o) "_CFURLCopyFileSystemPath", referenced from: _SQLDriverConnect_Internal in libodbc.a(connect.o) "_CFRelease", referenced from: _SQLDriverConnect_Internal in libodbc.a(connect.o) _SQLDriverConnect_Internal in libodbc.a(connect.o) "_CFStringGetCString", referenced from: _SQLDriverConnect_Internal in libodbc.a(connect.o) "_CFBundleGetBundleWithIdentifier", referenced from: _SQLDriverConnect_Internal in libodbc.a(connect.o) ld: symbol(s) not found collect2: ld returned 1 exit status cabal: Error: some packages failed to install: haskelldb-hdbc-odbc-0.13 failed during the building phase. The exception was: ExitFailure 1 Hints gratefully received!... Cheers Neil

1 0

ArrowCircuit, delay and space leaks
by Ben 02 Sep '10

02 Sep '10

Hello Arrow-theorists -- In a previous email Maciej Piechotka showed me how to construct a recursive function I wanted via ArrowCircuits. This computes the running sum of a stream of Ints. rSum :: ArrowCircuit a => a Int Int rSum = proc x -> do rec let next = out + x out <- delay 0 -< next returnA -< next Although this arrow runs in linear time, it exhausts the stack (I've compiled with ghc -02.) The obvious strict non-arrow version runs in linear time and constant space : rSum :: [Int] -> [Int] rSum = rSum' 0 where rSum' _ [] = [] rSum' n (x:xs) = let n' = x+n in n' `seq` n' : rSum n' xs It is ironic because arrows were used in the past to plug space leaks. It seems that using delay here introduces a growing stack of thunks. I have tried decorating everything I could think of with `seq` in the pointfree and pointed versions, to no avail. Is there a (pointed or point-free) version which runs in linear time and constant space? Best regards, Ben PS I tried manually translating the ArrowCircuit into a length-preserving stream function (SF in Hughes's paper) to try to understand what was going on. I ended up with rSum :: [Int] -> [Int] rSum xs = zipWith (+) xs $ 0 : rSum xs which is not quite right as it is quadratic. But I think it captures the basic idea of the translation.

1 1

Statically tracking "validity" - suggestions?
by strejon 02 Sep '10

02 Sep '10

Hello. I'm using Haskell to write a specification for some software. The software uses certificates (standard X.509 certificates) and stores user name information in the Subject's CommonName field. The X.509 standard doesn't actually require the presence of a CommonName field so the contents of the Subject section (with the rest of the fields omitted) are just represented by a Maybe User_Name. > import Data.List (find, concat) > import Data.Maybe (fromJust, isJust) > > type User_Name = String > type Public_Key = Integer > data Subject_Name = Subject_Name (Maybe User_Name) deriving (Show, Eq) > > data Certificate = Certificate { > certificate_subject :: Subject_Name, > certificate_key :: Public_Key, > certificate_issuer :: String, > certificate_serial :: Integer > } deriving (Show, Eq) This is all well and good, but the problem is that the validity of certificates isn't tracked statically and I have to use the following as guards on all functions that only expect valid certificates (and inevitably handle cases that I know can't actually happen but have to be handled in pattern matching and the like, bloating the specification): > user_name :: Subject_Name -> Maybe User_Name > user_name (Subject_Name name) = name > > is_valid :: Certificate -> Bool > is_valid = isJust . user_name . certificate_subject I'm aware of phantom types and the like, but I've been unable to work out how to use them (or another type system extension) to properly track "validity" on the type level. I'd want something like: validate :: Certificate Possibly_Valid -> Maybe (Certificate Valid) With later functions only accepting values of type "Certificate Valid". Is there a simple way to do this? -- View this message in context: http://old.nabble.com/Statically-tracking-%22validity%22---suggestions--tp2… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

8 8

questions about Arrows
by Ben 02 Sep '10

02 Sep '10

Hello -- Three related questions, going from most specific to most general : 1 ) Consider the stream processing arrow which computes a running sum, with two implementations : first using generic ArrowCircuits (rSum); second using Automaton (rSum2) : module Foo where import Control.Arrow import Control.Arrow.Operations import Control.Arrow.Transformer import Control.Arrow.Transformer.All rSum :: ArrowCircuit a => a Int Int rSum = proc x -> do rec out <- delay 0 -< out + x returnA -< out rSum2 = Automaton (f 0) where f s n = let s' = s + n in (s', Automaton (f s')) runAuto _ [] = [] runAuto (Automaton f) (x:xs) = let (y, a) = f x in y : runAuto a xs take 10 $ runAuto rSum [1..] [0,1,3,6,10,15,21,28,36,45] take 10 $ runAuto rSum2 [1..] [1,3,6,10,15,21,28,36,45,55] Note that the circuit version starts with the initial value zero. Is there a way to write rSum2 in the general ArrowCircuit form, or using ArrowLoop? 2) Are the ArrowLoop instances for (->), Kleisli Identity, and Kleisli ((->) r) all morally equivalent? (e.g., up to tagging and untagging?) 3) One can define fix in terms of trace and trace in terms of fix. trace f x = fst $ fix (\(m, z) -> f (x, z)) fix f = trace (\(x, y) -> (f y, f y)) undefined Does this mean we can translate arbitrary recursive functions into ArrowLoop equivalents? Best regards, Ben

2 3

open and closed
by Gábor Lehel 02 Sep '10

02 Sep '10

This is pure speculation, inspired in part by Brent Yorgey's blog post[1] from a few weeks ago. I'm wondering if it might be possible, in theory, to have both open and closed variants for each of value-level functions, type functions, and classes, in a fairly analogous way. (Maybe you could even have open (G)ADTs, which you would then need open functions to match on; or maybe a closed one with a case for _ to ensure exhaustiveness.) In each case you'd have the closed variant requiring you to keep all the definitions in the same module, permitting overlap, and trying to match definitions in the order they're listed; whereas the open variant would let you have definitions across modules, would forbid overlap (or would require definitions to be equivalent where they overlap, as with type families), and would always select the uniquely matching definition. Open value-level functions with this scheme would be inherently partial, which is bad. (It's not a problem at the type level because you just get a compile error if nothing matches, but an exception at runtime isn't so nice.) As a solution, perhaps it might be possible to allow a limited form of overlap (or don't even call it overlap) for the open variants: a default "use this is if nothing else matches" definition (which would need to be in the same module as the original class / type family declaration, or whatever ends up being analogous for open value-level functions, maybe the type signature). That way you could use Maybe for open value-level functions and make the default Nothing, among other options. Overlap in type functions allegedly makes typechecking unsound; I don't know if that would also hold in this more limited case. This would definitely break the property where adding or removing an import can't change the behaviour of a program other than whether it compiles, which is considered very important by many [2], so maybe it's not a good solution. (Possibly you could add explicit import/export control for instances/other-open-things to alleviate this, in a way so that definitions for open thingies with default definitions (at least) would always have to imported explicitly, thereby acknowledging that it might change behaviour... or maybe that would be a bandaid too far, I dunno.) (I think this would also cover most (if not all?) of the use cases for OverlappingInstances, which permits overlap and selects the most specific instance in a more general fashion; but maybe that doesn't matter if the two are equally bad, I don't know. I'm not 100% clear on peoples' opinion of OverlappingInstances, but I as far as I know the problems are twofold: both import-unsafeness, and the matter of how you would actually define "most specific" in a way that's both rigorous and intuitive; this would remove at least the latter.) Anyway, thoughts? Is this all completely crazy and way out there? [1] http://byorgey.wordpress.com/2010/08/05/typed-type-level-programming-in-has… [2] http://hackage.haskell.org/trac/haskell-prime/wiki/LanguageQualities -- Work is punishment for failing to procrastinate effectively.

3 5

ICFP Hotel Room
by Michael D. Adams 02 Sep '10

02 Sep '10

Hi all, I'm a graduate student (male) and am looking for a (male) roommate to split the cost of a hotel room at ICFP. If anyone is interested in splitting a room, please drop me a line. I will be attending the workshops collocated with ICFP so I currently have a reservation at the conference hotel (at the conference rate) with check-in on September 24 (the day before the first workshop) and check-out on October 3 (the day after the last workshop). Michael D. Adams Ph.D. Student, Indiana University

2 2

ANN: Hayoo! 2.1
by "Timo B. Hübel" 01 Sep '10

01 Sep '10

Hi, We are pleased to announce the next major release 2.1 of Hayoo!, the Haskell API search engine with find-as-you-type and suggestions. Visit Hayoo! here: http://holumbus.fh-wedel.de/hayoo What's new? Thanks to Uwe Schmidt, we have completely revamped the indexer, which now also crawls package information from Hackage. Hence, Hayoo! now searches package names, package categories, package descriptions etc., too, and shows you some package results along with the functions found (some of you may have noticed this already, since this is live for testing purposes since a few months). For example, this will find you all packages in the category "Algorithms" that will do something with "sat": category:algorithms sat This will find you some strict datastructures (i.e. synopsis contains "strict" and category contains "data"): synopsis:strict category:data As we now have package information present in the search index, the algorithm for ranking the results has been adjusted to mainly depend on reverse package dependencies. Nevertheless, we are still trying to optimize this. The new indexer also supports incremental index updates, which made a rebuild of the whole infrastructure around it possible. This way, we are now able to provide daily index updates. Useful figures about the current index are shown below the query input field. Additionally, we have made some optimizations and performance improvements. This allowed us to leverage the restrictions on the query length and hence it is now possible to search for any single character (try searching for "s"). In the result display, the whole function description is now included and its formatting is preserved. Internally, the HTML rendering part has been completely rewritten, which hopefully allows for faster adoption of new features. Please let us know about any issues or suggestions. Especially some opinions about how to integrate the package information in the result display would be appreciated. Thanks, Timo

1 0

Announce: Significant performance improvements for Data.Map
by Don Stewart 01 Sep '10

01 Sep '10

http://hackage.haskell.org/trac/ghc/ticket/4277 Proposal: Significant performance improvements for Data.Map Description Milan Straka's recent [52] Haskell Symposium paper (PDF) shed light on the containers:Data.Map library, indicating there were both algorithmic and stylistic performance improvements to be made. 52. http://research.microsoft.com/~simonpj/papers/containers/containers.pdf This proposal provides a patch that [53] dramatically improves performance across the API. Three standard techniques are applied to the code: * [54] Worker/Wrapper transformations of recursive functions with constant arguments (aka. the [55] static argument transformation). * Explicit inlining of wrapper functions. * Explicit strictness of keys to functions. 53. http://is.gd/eJHIE 54. http://www.workerwrapper.com/ 55. http://hackage.haskell.org/trac/ghc/ticket/888 Three complementary, but orthogonal patches are provided. 1. Add a testsuite, [56] with coverage data (currently 91% of top level functions, and all core functions). 2. Add a micro-benchmark suite based on [57] Criterion, for empirical evidence of improvements to each function. 3. The optimization patch itself. All 3 patches should be applied, under this proposal. 56. http://code.haskell.org/~dons/tests/containers/hpc_index.html 57. http://hackage.haskell.org/package/criterion The [58] benchmark results are very strong: * An average speedup across the core api of 47% (on intel i7 / linux 64 bit), and; * 36% on Mac / intel core 2 duo 32 bit). http://i.imgur.com/05BWe.png 58. http://is.gd/eJHIE No bugs were identified in the development of the comprehensive testsuite, which includes a large set of unit tests from [60] Kazu Yamamoto 60. http://twitter.com/kazu_yamamoto/status/22351727559 A fork of the containers package, with the 3 patches (and a version bump to make it easier to test out) is available: darcs get http://code.haskell.org/~dons/code/containers/ Separately, the patches are attached to this ticket. The consideration period is 3 weeks (before ICFP). __________________________________________________________________ Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan Tibell and Don Stewart.

4 5

:Trace has no history
by Steve 01 Sep '10

01 Sep '10

I am trying to debug a problem in GHCI. I invoke my method with trace but when it breaks on exception i can't get this history. Output is below. Thanks. relude Symbols> :set -fbreak-on-exception Prelude Symbols> :trace myMethod Loading package HUnit-1.2.2.1 ... linking ... done. Loading package syb-0.1.0.2 ... linking ... done. Loading package base-3.0.3.2 ... linking ... done. Loading package old-locale-1.0.0.2 ... linking ... done. Loading package time-1.1.4 ... linking ... done. Loading package random-1.0.0.2 ... linking ... done. Loading package QuickCheck-1.2.0.0 ... linking ... done. Loading package Decimal-0.1.0 ... linking ... done. Loading package array-0.3.0.0 ... linking ... done. Loading package Diff-0.1.2 ... linking ... done. Loading package bytestring-0.9.1.5 ... linking ... done. Loading package containers-0.3.0.0 ... linking ... done. Loading package mtl-1.1.0.2 ... linking ... done. Loading package old-time-1.0.0.3 ... linking ... done. Loading package convertible-1.0.9 ... linking ... done. Loading package utf8-string-0.3.4 ... linking ... done. Loading package HDBC-2.2.6 ... linking ... done. Loading package HDBC-mysql-0.6.3 ... linking ... done. Loading package parsec-2.1.0.1 ... linking ... done. Loading package network-2.2.1.7 ... linking ... done. Loading package HTTP-4000.0.9 ... linking ... done. Loading package binary-0.5.0.2 ... linking ... done. Loading package digest-0.0.0.8 ... linking ... done. Loading package filepath-1.1.0.3 ... linking ... done. Loading package unix-2.4.0.0 ... linking ... done. Loading package directory-1.0.1.0 ... linking ... done. Loading package pretty-1.0.1.1 ... linking ... done. Loading package zlib-0.5.2.0 ... linking ... done. Loading package zip-archive-0.1.1.6 ... linking ... done. Loading package Core-0.0.1 ... linking ... done. Beginning Update Stopped at <exception thrown> _exception :: e = GHC.Exception.SomeException (GHC.Exception.D:Exception _ (GHC.Show.D:Show ...) ....) (GHC.IO.Exception.IOError Nothing GHC.IO.Exception.UserError ....) [<exception thrown>] Prelude Symbols> :history Empty history. Perhaps you forgot to use :trace?

3 3