March 2017 - Haskell-Cafe

Code/style review
by Jan von Löwenstein 24 Mar '17

24 Mar '17

Hi, TL;DR I am pretty new to Haskell and have some Haskell code I'd love to get feedback on. ( https://github.com/SAP/bosh-cpi-haskell/tree/a586079dd9383fca030f1536116522… and https://github.com/SAP/bosh-kubernetes-cpi-release/tree/master/src/bosh-kub… ) Longer version: I started looking into Haskell back in November last year. Pretty soon I wanted to try something more "real-world" IO heavy in order to see how that goes. I came up with a side-project at work to implement a Bosh Kubernetes CPI. Bosh (bosh.io) is a tool to install and manage distributed systems on a range of IaaSs. In particular it is used to install Cloud Foundry (a cloud application development platform). I guess I don't have to introduce Kubernetes. The interface between Bosh and its cloud provider interfaces (CPI) is a simple command line application. Bosh provides configuration via file provided as process call argument. It provides the method to be invoked including arguments as JSON via stdin and expects a response via stdout. The CPI can provide a log via stderr. (http://bosh.io/docs/cpi-api-v1.html) The interface to Kubernetes is basically a REST api, i.e. http calls. Currently I use a generated client based on Servant ( https://github.com/soundcloud/haskell-kubernetes) I have put that interface into its own package. I created two typeclasses FileSystem[1] and System[2] to abstract away the system (I guess I should call them MonadFileSystem and MonadSystem to align with how mtl calls the monadic classes). And I created another typeclass MonadCpi[3] to abstract away the concrete implementation towards potentially several infrastructures. The Kubernetes implementation[4] is rather hacked (no tests, low testability, etc.) and I'd like to change that. I thought about a typeclass for REST resources (with methods create, get, list, update, delete, ...) and I begin to have problems integrating that into my current primitives (e.g. I'd like to have a MonadLog instance that uses my System typeclass for printing to stderr). That's when I started to ask myself if I had chosen the right Haskell tools and primitives for what I was doing and thought it was time to get some feedback from more experienced Haskellers aka you. I know this was a pretty long text. Sorry for that. Any feedback, including "you did it completely wrong" is appreciated - as long as it includes "have a look here and here", "look this is what I would do", or similar. Many thanks already for reading. Best Jan [1] https://github.com/SAP/bosh-cpi-haskell/blob/a586079dd9383fca030f1536116522… <https://github.com/SAP/bosh-cpi-haskell/blob/a586079dd9383fca030f1536116522…> [2] https://github.com/SAP/bosh-cpi-haskell/blob/a586079dd9383fca030f1536116522… [3] https://github.com/SAP/bosh-cpi-haskell/blob/a586079dd9383fca030f1536116522… [4] https://github.com/SAP/bosh-kubernetes-cpi-release/blob/master/src/bosh-kub…

1 0

Code Review Request - Unbalanced Parenthesis correction
by Michael Litchard 24 Mar '17

24 Mar '17

I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses. The finger tree seems to be the right data structure. As a proof of concept I've used Data.Sequence to test my idea. If this is the right direction to go, I'll write more specialized finger tree code. The code works on the few test cases I have tried. Feedback appreciated. {-# LANGUAGE ViewPatterns #-}module Parenthesis whereimport BasicPrelude hiding (concat,null,empty) import Data.Sequence hiding (length)import Data.Foldable hiding (length,null) balanceParens :: String -> String balanceParens str = go str [] empty where go [] [] (null -> True) = [] go [] [] parens = Data.Foldable.toList parens go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(') go (')':xs) [] (null -> True) = go xs [] (fromList "()") go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(') go (')':xs) [] parens = go xs [] corrected where corrected = ('(' <| parens) |> ')' go (')':xs) (RP:debit) parens = go xs debit (parens |> ')') go (_:xs) debit parens = go xs debit parens go [] (RP:debit) parens = go [] debit (parens |> ')') example: balanceParens "))(""(())()" balanceParens ")))""((()))"

7 13

Why does "enumFromThenTo x x y" depend on "y"?
by Clinton Mead 24 Mar '17

24 Mar '17

I'm implementing Enum for a type I have, and I figured it should replicate what ordinary Enum types, so I did some tests on how Enum behaves. I noticed that: "enumFromThenTo 3 3 5" is not the same as "enumFromThenTo 3 3 1". This seems bizarre to me. Generally increasing the stepsize increases the length of the list. For example, "length (enumFromThenTo 0 10 1000) == 101" "length (enumFromThenTo 0 2 1000) == 501" "length (enumFromThenTo 0 1 1000) == 1001" "length (enumFromThenTo 0 0 1000) == infinite" but "length (enumFromThenTo 0 (-10) (-1000)) == 101" "length (enumFromThenTo 0 (-2) (-1000)) == 501" "length (enumFromThenTo 0 (-1) (-1000)) == 1001" "length (enumFromThenTo 0 0 1000) == 0" It would seem to me that "enumFromThenTo x y z == map negate (enumFromThenTo (-x) (-y) (-z))" should be an invariant that should hold but in this case it clearly doesn't. Is this intentional, and if so, for what reason? Or is this a GHC bug?

2 1

One-Off detection. Question about Space/Time complexity
by Michael Litchard 23 Mar '17

23 Mar '17

Problem spec from CareerCup <https://careercup.com/question?id=5092486548553728>. Given two strings, return boolean True/False if they are only one edit apart. Edit can be insert/delete/update of only one character in the string. Eg. -True xyz,xz xyz,xyk xy,xyz -False xyz,xyz xyz,xzy x,xyz module Strings.OneLetter where` import Preludeimport qualified Data.Text as T` oneLetter :: T.Text -> T.Text -> Bool oneLetter s1 s2 | s1 == s2 = False | max_l > (min_l + 1) = False | max_l == min_l = diff_size == 1 | otherwise = diff_size == 0 where length_s1 = T.length s1 length_s2 = T.length s2 max_l = max length_s1 length_s2 min_l = min length_s1 length_s2 diff_size = length $ filter (\(a,b) -> a /= b) zipped zipped = T.zip s1 s2` So, I used Text instead of String, hoping I could take advantage of fusion. I have the following questions and my initial attempt to answer them. What is the time complexity of oneLetter 0(m+n) where m is the length of s1 and n is the length of s2 what is the space complexity of oneLetter? I'm thinking due to laziness it's O(1), only two Chars are in memory at any one time, or two Ints. But I'm hazy on why. If this is wrong, please articulate why. If I'm right, and my reasoning is wrong or incomplete, please say why. I don't think I can improve the time complexity. Am I right? Can the space complexity be improved? What if I changed from Text to String? I don't think the time complexity changes, but how does this change the space complexity?

4 6

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

23 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 22 Mar '17

22 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 22 Mar '17

22 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