- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] One-Off detection. Question about Space/Time complexity
by Olaf Klinke 24 Mar '17

24 Mar '17

I believe this is the classic publication on the subject: http://users.monash.edu/~lloyd/tildeStrings/Alignment/92.IPL.html The Haskell implementation is here: http://users.monash.edu/~lloyd/tildeFP/Haskell/1998/Edit01/ In case of a pair of one-off strings, it is O(m) time. Not sure whether the entire strings are kept in memory. My gut feeling is that they must be kept in memory in the worst case (edit distance max(m,n)) but stretches of matched prefixes can be garbage collected. So in your particular case it should indeed be O(1) space. Profiling suggests the algorithm is not O(1) space, but I might have done the input strings wrong. input :: Int -> String input = flip replicate 'a' length . input should be O(1) space, shouldn't it? With ghc 7.8.3 and -O2 it is not. Running the edit distance on the pair (input m, 'b' : input m) and profiling the program suggests the algorithm is O(m) space. Andrew Butterfield's oneOff seems to be linear space, too. -- Olaf $cat test.hs import System.Environment import Data.List (foldl') import EditDistance (d) input :: Int -> String input n = replicate n 'a' main = do args <- getArgs let n = read (head args) let x = input $! (n+1) let y = 'b' : input n print (d x y) $ghc -O2 --make -prof -fprof-auto test.hs [2 of 2] Compiling Main ( test.hs, test.o ) Linking test ... $for n in 1000 10000 100000; do ./test $n +RTS -p && grep 'total alloc' test.prof; done 1 total alloc = 358,128 bytes (excludes profiling overheads) 1 total alloc = 3,022,696 bytes (excludes profiling overheads) 1 total alloc = 29,663,256 bytes (excludes profiling overheads)

1 0

Num nstances for Data.Monoid.{First,Last}
by Oliver Charles 23 Mar '17

23 Mar '17

We already have Num instances on things like Sum and Product, could we have them on First and Last? I mostly want fromInteger on these types. To give you a real world example: keySpeed :: L.Fold KeyboardEventData Double keySpeed = L.foldMap (\KeyboardEventData {keyboardEventKeyMotion} -> case keyboardEventKeyMotion of Pressed -> Last (Just 1) Released -> Last (Just 0)) (fromMaybe 0 . getLast) keySpeed folds (under Control.Foldl) events from a UI system into the number 1 if the key has been pressed and 0 if the key has been released. It's OK in the above form, but if Last had a Num instance, I could just have Pressed -> 1 Released -> 0 Which I find preferable. Any thoughts? - Ollie

1 0

GHC 8.0.2 and extra dynamic libraries
by Bryan Gardiner 23 Mar '17

23 Mar '17

Hi all, I'm not sure if this is the right place to ask this, but I'd like to see if there were any changes between GHC 8.0.1 and 8.0.2 in how linking works on Linux. I inject an extra library directory (extraLibDirs, for building qtah) via preBuild and preTest Cabal hooks[1], and while GHC 8.0.1 (or is this Cabal?) seems to pass this as both "-L$dir" and "-optl-Wl,-rpath,$dir" to the ghc link command, GHC 8.0.2 (Cabal?) appears to only pass the former, causing the built library to be unable to find its dependency in that directory. Is this a known change? Do I need to pass -optl-Wl,... myself now? I'm running Gentoo with the Haskell overlay, Cabal-1.24.2.0, and cabal-install-1.24.0.2 in both cases. Happy to provide more info if necessary. Thanks for any help you can provide, Bryan [1] https://gitlab.com/khumba/qtah/blob/master/qtah/Setup.hs

1 0

Fwd: Semigroup and Monoid instances for ReaderT
by David Menendez 23 Mar '17

23 Mar '17

On Tue, Mar 21, 2017 at 3:53 AM, Louis Pan <louis(a)pan.me> wrote: > Hi all, > > In my Glazier GUI library, I had to use newtype wrappers to create > Semigroup and Monoid instances for ReaderT. > > Is there a reason why ReaderT doesn't have an instance of Semigroup and > Monoid? > There are at least three reasonable instances of Semigroup and Monoid for ReaderT. instance (Applicative m, Monoid a) => Monoid (ReaderT r m a) where mempty = pure mempty mappend a b = mappend <$> a <*> b instance (Alternative m) => Monoid (ReaderT r m a) where mempty = empty mappend = (<|>) instance (Monoid (m a)) => Monoid (ReaderT r m a) where mempty = ReaderT $ mempty mappend a b = ReaderT $ mappend a b In the absence of a principled reason to prefer one over the others and a general consensus, I think it’s better not to choose. -- Dave Menendez <dave(a)zednenem.com> <http://www.eyrie.org/~zednenem/>

2 1

Semigroup and Monoid instances for ReaderT
by Louis Pan 22 Mar '17

22 Mar '17

Hi all, In my Glazier GUI library, I had to use newtype wrappers to create Semigroup and Monoid instances for ReaderT. Is there a reason why ReaderT doesn't have an instance of Semigroup and Monoid? The reader ((->) a) is a Monoid and a Semigroup. https://hackage.haskell.org/package/base-4.9.1.0/docs/src/ GHC.Base.html#line-268 https://hackage.haskell.org/package/base-4.9.1.0/docs/src/ Data.Semigroup.html#line-150 Could the following be added to the transformers package? Or is it not lawful? instance (Applicative m, Semigroup a) => Semigroup (ReaderT r m a) where f <> g = (<>) <$> f <*> g {-# INLINABLE (<>) #-} instance (Applicative m, Monoid a) => Monoid (ReaderT r m a) where mempty = pure mempty {-# INLINABLE mempty #-} f `mappend` g = mappend <$> f <*> g {-# INLINABLE mappend #-} Does it make sense to extend the monoid instance to all the other transformers? Eg. instance (Monad m, Semigroup a) => Semigroup (StateT s m a) where f <> g = (<>) <$> f <*> g {-# INLINABLE (<>) #-} instance (Monad m, Monoid a) => Monoid (StateT s m a) where mempty = pure mempty {-# INLINABLE mempty #-} f `mappend` g = mappend <$> f <*> g {-# INLINABLE mappend #-} instance (Monad m, Monoid w, Semigroup a) => Semigroup (WriterT w m a) where f <> g = (<>) <$> f <*> g {-# INLINABLE (<>) #-} instance (Monad m, Monoid w, Monoid a) => Monoid (WriterT w m a) where mempty = pure mempty {-# INLINABLE mempty #-} f `mappend` g = mappend <$> f <*> g {-# INLINABLE mappend #-} and also for MaybeT, IdentityT, ExceptT, etc Regards, Louis

2 2

Full-time (remote acceptable) -- Haskell engineering at Vacation Labs, India
by Saurabh Nanda 22 Mar '17

22 Mar '17

Cross-posted from Reddit: https://www.reddit.com/r/haskell/comments/60tkh7/fulltime_remote_acceptable… We are a startup based out of Goa (India), building travel-related technology products. Our flagship SaaS product is already in the market and has paying customers. We're expanding our product portfolio, and building new products in Haskell (the current product is written in Rails + AngularJS). If you're interested in using Haskell (and related FP languages, like Elm & Purescript) to build web/mobile products, do apply via http://www.vacationlabs.com/we-are-hiring/software-engineer-haskell/ PS: Our current stack is Rails, AngularJS v1, Postgres, Redis, Bootstrap+LessCSS. The stack for future product-dev is Haskell (on the server) with Typescript/Elm/Purescript (on the UI). -- Saurabh.

1 0

Semigroup and Monoid instances for ReaderT
by Olaf Klinke 22 Mar '17

22 Mar '17

Maybe I missed something, but aren't the transformers a red herring here? instance (Semigroup a, Applicative f) => Semigroup (f a) where (<>) = liftA2 (<>) My first guess was that you could add this instance to your code without the need for changes to the transformers package. The problem with the semigroup instance above is that it conflicts with semigroup instances for f. For example, there is a semigroup instance for [a] when a is not a semigroup. For the declaration above, ghci 7.8.3 gave me: Overlapping instance declarations: instance (Semigroup a, Applicative f) => Semigroup (f a) -- Defined at <interactive>:4:10 instance (Semigroup a, Semigroup b) => Semigroup (a, b) -- Defined in ‘Data.Semigroup’ Hence I guess you must use a newtype wrapper to declare when you want the semigroup instance of a and when you want the instance of f. Olaf

1 0

Registration Open: Compose 2017, New York, May 18-19
by Gershom B 21 Mar '17

21 Mar '17

http://www.composeconference.org/2017 Compose is a conference for typed functional programmers, focused specifically on Haskell, OCaml, F#, SML, and related technologies. It will be held in New York on Thursday and Friday, May 18-19, 2017. Early Bird registration is now open at eventbrite: https://www.eventbrite.com/e/cmpse-conference-2017-tickets-32106159387 Additionally, we're happy to announce our keynote speaker as Emily Riehl, who is a professor of mathematics at Johns Hopkins University, and the author of the book Category Theory in Context (as well as much else). To get a sense of Compose, you can check out the great talks from past conferences: https://www.youtube.com/channel/UC0pEknZxL7Q1j0Ok8qImWdQ Finally, as a reminder, the Call for Presentations closes on March 23, so hurry up and get those talk proposals submitted! http://www.composeconference.org/2017/cfp/ Cheers, Gershom

1 0

Has anyone used Graql in Haskell?
by Jeffrey Brown 20 Mar '17

20 Mar '17

Graql[1] is a (and stands for) graph query language. It is unusually expressive, allowing relationships to be members of other relationships[2] -- effectively, allowing one edge to be an endpoint of another edge. Someone named Felix posted a Haskell library for generating Graql queries[3]. Does anyone have a Haskell program that not only generates but uses such a query? [1] https://hackage.haskell.org/package/graql [2] https://discuss.grakn.ai/t/nested-relationships/ [3] https://discuss.grakn.ai/t/graql-haskell-how-to-run-the-test-program/ -- Jeff Brown | Jeffrey Benjamin Brown Website <https://msu.edu/~brown202/> | Facebook <https://www.facebook.com/mejeff.younotjeff> | LinkedIn <https://www.linkedin.com/in/jeffreybenjaminbrown>(spammy, so I often miss messages here) | Github <https://github.com/jeffreybenjaminbrown>

4 5

Best practices for linting wrt performance
by Adam Bergmark 20 Mar '17

20 Mar '17

I'd like to make aeson hlint clean. aeson contains a lot of performance optimizations which made me wonder; Which linting refactorings should you think twice about when it comes to performance? The best way to find an answer to this for aeson is of course to run the benchmarks, but are there any rules-of-thumb that you take into account when linting? Here's the default hlint output for the current aeson master: https://gist.github.com/bergmark/5dd63c24fe6bdcf67eae0e88495a24e7 Cheers, Adam

3 6