- Haskell-Cafe - Haskell.org

Proposal for an extension: in-module namespaces
by Aura Kelloniemi 28 Mar '17

28 Mar '17

Hello I've been thinking about an extension to GHC which would allow creating new module-like namespaces within normal Haskell modules. Because this kind of namespacing system seems quite obvious to me, I ask if it has already been proposed or discussed in detail? The motivation: 1. It would assist in solving the 'pollution of namespace' -problem, of which many Haskellers have complained. 2. It would allow building bundles of related modules which can be exported from one module and then imported into others. This could result in radically fewer import statements. Rant: I'm tired of writing import qualified Data.ByteSstring as B import qualified Data.ByteString.Builder as B import qualified Data.ByteString.Lazy as BL import qualified Data.ByteString.Lazy.Builder as BL import qualified Data.HashMap.Strict as HM import qualified Data.Text as T import qualified Data.Text.Lazy as TL import qualified Data.Text.Lazy.Builder as BL A huge portion of this appears in almos all my Haskell source files. If I wrote my code in Python, I could condense all these imports to: So, you see, it was zero lines of code. I'm also tired of these patterns: (personName p), (companyName c), (objectName o), ... and I hardly prefer (name (p :: Person)), (name (c :: Company)) or (name (o ::Object)) using the DuplicateRecordFields syntax. Proposal: I propose that modules can contain named submodules. They can be exported and imported just like anything else within a module, like this: {-# LANGUAGE Submodules #-} module Library.Things (qualified module Person, qualified module Company, personWorksInCompany ) where -- import ... qualified module Person (Person (..)) where -- This is the module Library.Things.Person. Submodules could possibly -- use some other keywords than 'qualified module'. Maybe just 'module', -- 'submodule' or 'namespace'. data Person = Person { name :: {-# UNPACK #-} !T.Text, id :: {-# UNPACK #-} !Unique, ... } -- Back in Library.Things qualified module Company where data Company = Company { name :: {-# UNPACK #-} !T.Text, employees :: {-# UNPACK #-} !V.Vector Unique, ... } -- back in Library.Things again: personWorksIn :: Person.Person -> Company.Company -> Bool personWorksIn p c = Person.id p `elem` Company.employees c -- ... end of Library.Things And in another file: {-# LANGUAGE Submodules #-} -- The following demonstrates some ways of importing submodules. They are -- not meant to be used like this in real code: import Library.Things import qualified Library.Things as Things -- Now the submodules are also in scope and can be referred to like this: person1 :: Person.Person person2 :: Things.Person.Person company :: Library.Things.Company.Company -- And we also could have written: after importing Library.Things: import Person -- And now data type Person, selector name, etc. are in scope -- If we also imported the Company module: import Things.Company -- selector 'name' would now be ambiguous and need qualification at use site. -- Import lists would also work when bringing submodule contents to current -- namespace. Like this: import Library.Things hiding (module Company) -- or import qualified Library.Things (module Person) -- Which would allow Library.THings.Person.Person to be used requiring use of -- the fully qualified name. -- But the following would not work if Library.Things was not already -- imported: import Library.Things.Person -- because there is no such module, just submodule. -- ... end of other file Some projects probably would like to create a module like this: module Imports (qualified module B, qualified module HM, qualified module T ) where import Data.ByteString as B -- ... and so forth ... Open questions: - Should there be a separate keyword for importing submodules, for example 'use' or 'import namespace'? - Would imports be allowed within submodules? I'd say no for importing other modules, but importing submodules could be ok. - Would it be possible to extend submodules after their initial definition by just writing a new 'qualified module' block? I'd say yes, because submodules are just about namespacing. It is today possible to import many modules qualified and put them in the same namespace, like is often done. - What do you fellow Haskellers think about this all? -- Aura

6 7

Two PhD positions in Ljubljana starting October 2017
by Matija Pretnar 28 Mar '17

28 Mar '17

We are looking for two PhD students at the Faculty of Mathematics and Physics, University of Ljubljana. The programme starts in October 2017 and lasts three years. The positions will be fully funded (subject to approval by the funding agency). The candidates should have a Master's degree in mathematics or computer science. No knowledge of Slovene is required. The first PhD student will be advised by dr. Andrej Bauer. The topic of research is foundations of type theory. The candidate should have interest in mathematical aspects of type theory, and familiarity with proof assistants is desirable. The second PhD student will be advised by dr. Matija Pretnar. The topic of research is the theory of programming languages with a focus on computational effects. The candidate should have interest in both the mathematical foundations and practical implementation of programming languages. Candidates should send their applications as soon as possible, but no later than the end of April, to Andrej Bauer <andrej.bauer(a)fmf.uni-lj.si> or Matija Pretnar <matija.pretnar(a)fmf.uni-lj.si>, depending on their primary interest. Please include a short CV, academic record, and a statement of interest. Andrej Bauer and Matija Pretnar

1 0

Munich Haskell Meeting, 2017-03-29 @ 19:30
by Christian Neukirchen 26 Mar '17

26 Mar '17

Dear all, Next week, our monthly Munich Haskell Meeting will take place again on Wednesday, March 29 at Max-Emanuel-Brauerei at 19h30. For details see here: http://muenchen.haskell.bayern/dates.html If you plan to join, please add yourself to this dudle so we can reserve enough seats! It is OK to add yourself to the dudle anonymously or pseudonymously. https://dudle.inf.tu-dresden.de/haskell-munich-mar-2017/ Everybody is welcome! cu, -- Christian Neukirchen <chneukirchen(a)gmail.com> http://chneukirchen.org

1 0

Void vs ()
by Bardur Arantsson 25 Mar '17

25 Mar '17

Hi all, [Context: I'm working on a CQRS/ES library and in the following, "i" is an identifier for an aggregate root, "e" is an event type, and the "Int" is a sequence number.] So, I have a data type data Foo i e = Foo i e Int where I want to have a corresponding data Batch i e = Batch i [Foo x e Int] (I'll come back to "x". It's just a metasyntactic variable for now. The point of the "Int" is that it's extra information that I really need to keep, but it's not essential to the Foo data structure itself.) with an operation batchFoos :: [Foo i e] -> [Batch i e] batchFoos = ... (basically a standard Data.List.groupBy where I compare for equality on the i's.) I also have an extraction function toList :: Batch i e -> (i, [Foo x e Int]) My question is then: What's the best thing to use for "x", Void or ()? The idea behind "collapsing" the "i" parameter away to an "x" is to signal to users to the API that they can be absolutely certain that when they call "toList", they can be sure that all the Foo's that they get back have the same i value, namely the one which is the first component of the tuple. An alernative I've been considering is actually to create a Foo' type which actually does eliminate the i parameter, but it seems a bit boilerplatey. (It's not a *lot* of code to duplicate, so if it looks like the best option, I'll do that... but it feels odd.) Anyone have any suggestions on what the best way to approach this would be? (Aside: AFAICT there's no reasonable way to implement anything like Foldable or Traversable to avoid the explicit "toList" function, right? AFAICT Foldable/Traversable constrain you to using the *actual* last type parameter, "e", for folding over. Are there any generic alternative type classes that let you "pick your own element type"? I'm guessing Traversal could possibly be that, but if I have to incur a Lens dependency, I'll just live with a "toList" function. This is just about whether it can be done elegantly -- it's not a big deal.) Regards,

4 7

Literate Haskell w/ markdown?
by David Banas 25 Mar '17

25 Mar '17

Hi all, Would anyone care to share their preferred method for writing/processing literate Haskell w/ markdown? Thanks, -db

3 2

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