August 2015 - Haskell-Cafe

Folding part of a graph, and FGL's gfold function.
by Jeffrey Brown 13 Aug '15

13 Aug '15

Given a node N and an edge label L, I want to do things like "find N, and all of N's L-children, and all of their L-children ... and add up their values". Ideally the fold would not traverse the whole graph. (Note that in general, the subgraph induced by N and L-succession is not a tree.) Writing the fold myself, I can only imagine a very inefficient solution -- I would find each of N's L-children first, collect them, then find each of theirs, etc. In Data.Graph.Inductive.Basic, FGL provides a function called "gfold". This is its type signature: -- | Directed graph fold. gfold :: (Graph gr) => (Context a b -> [Node]) -- ^ direction of fold -> (Context a b -> c -> d) -- ^ depth aggregation -> (Maybe d -> c -> c, c) -- ^ breadth\/level aggregation -> [Node] -> gr a b -> c Is it what I'm looking for? If so, how does it work?

2 1

FGL: The cost and propoer way of changing the label at a node.
by Jeffrey Brown 13 Aug '15

13 Aug '15

Is changing the label at a node O(N)? The only way I can think of to do it is with a map, like the following -- which works, but seems like its speed must be linear in the number of nodes of the graph: > :m Data.Graph.Inductive.Example Data.Graph.Inductive.Graph > let f c@(adjIn, node, lab, adjOut) = case node of {1 -> (adjIn, node, 'b', adjOut); _ -> c} > loop mkGraph [(1,'a')] [(1,1,())] > gmap f loop mkGraph [(1,'b')] [(1,1,())] > Is that in fact the right way? Am I somehow missing the point of FGL if I have to do a lot of that?

2 4

Internship Opportunity at Galois: Winter/Spring 2016
by Ryan Wright 13 Aug '15

13 Aug '15

Galois has some exciting opportunities for interns in software research and engineering for the Winter/Spring of 2016. Most of our projects use Haskell to some extent, so this is a great chance to get experience applying functional programming to important real-world problems. Please pass along this posting to anyone you think might be interested--even if they don't yet know Haskell! Thank you, Ryan Wright # Galois Software Engineering/Research Intern # Galois is currently seeking software engineering and research interns for Winter/Spring 2016 at all educational levels. We are committed to matching interns with exciting and engaging engineering work that fits their particular interests, creating lasting value for interns, Galois, and our community. A Galois internship is a chance to tackle cutting-edge, meaningful problems in a uniquely collaborative environment with world-leading researchers. Roles may include technology research and development, requirements gathering, implementation, testing, formal verification, and infrastructure development. Past interns have integrated formal methods tools into larger projects, built comprehensive validation suites, synthesized high-performance cryptographic algorithms, written autopilots for quad-copters, designed the syntax and semantics of scripting languages, and researched type system extensions for academic publication. We deeply believe in providing comprehensive support and mentorship to all of our employees, particularly interns. We provide our employees with a steward who regularly checks in to ensure that they feel welcome and safe in the Galois community while gaining real value from their experiences. ## Important Dates ## Applications due: October 1st, 2015 Internship period (flexible): January through April, 2016 ## About Galois ## Our mission is to create trustworthiness in critical systems. We’re in the business of taking blue-sky ideas and turning them into real-world technology solutions. We’ve been developing real-world systems for over ten years using functional programming, language design, and formal methods. Galois values diversity. We believe that differing viewpoints and experiences are essential to the process of innovation. We look broadly, including outside of established communities, to deliver innovation. ## How to Prepare ## An internship is an opportunity for learning and growth as an engineer. To make the most of the opportunity, we ask that candidates have experience reading, writing, and maintaining code in a realistic project. Many university courses involve multi-week collaborative projects that provide this type of experience. Most of our projects use the Haskell programming language and the git version control system. These tools aren’t often taught in computer science classes, but there are many free resources available that we recommend for learning: - [Learn You a Haskell] for Great Good! [1] by Miran Lipovača - [Real World Haskell] [2] by Bryan O’Sullivan, Don Stewart, and John Goerzen - [tryGit] [3] by Code School - [Pro Git] [4] by Scott Chacon [1]: http://learnyouahaskell.com/ [2]: http://book.realworldhaskell.org/ [3]: http://try.github.io [4]: http://git-scm.com/book ## Qualifications ## The ability to be geographically located in Portland during the internship Experience reading, writing, and maintaining code in a project as described above Proficiency in software development practices such as design, documentation, testing, and the use of version control Well-developed verbal and written communication skills; comfort in a collaborative team environment The following skills are not required, but may be relevant to a particular project. - Proficiency in Haskell or other programming languages with rich type systems (eg., OCaml, Standard ML, Scala) - Experience using C and assembly languages for low-level systems programming - Development experience in high assurance systems or security software - Specific experience in an area of Galois’ expertise, such as: - Assured information sharing - Software modeling and formal verification - Cyber-physical systems and control systems - Operating systems, virtualization and secure platforms - Networking and mobile technology - Cyber defense systems - Scientific computing - Program analysis and software evaluation - Web security ## Logistics ## The length and start date of the internship are negotiable: starting any time from the new year through next spring is acceptable, but an intern must be at Galois for at least three continuous months. The internship is paid competitively, and interns are responsible for living arrangements (although we can certainly help you find arrangements). Galois is located in the heart of downtown Portland with multiple public transportation options available and world-class bicycle infrastructure. ## Application Details ## We’re looking for people who can invent, learn, think, and inspire. We reward creativity and thrive on collaboration. If you are interested, please send your cover letter and resume to us via http://galois-inc.hiringthing.com.

1 0

Standards-conform CSS tokenizer
by Tomas Carnecky 13 Aug '15

13 Aug '15

Recently I wrote a CSS tokenizer based on the css-syntax spec (the same standard that Blink now uses to parse CSS). The detailed description of my motivation is in the readme, but if I had to describe it in a sentence: The existing Haskell parsers were too high-level for me needs, they provided too much abstraction. The package does not implement the full parser, at least one token type is not implemented. But it should be able to tokenize most CSS files. I copied the tests from the Blink source. All but one pass (and of course the tests for the token types that are not implemented) While the spec describes the algorithm in a way that pretty much prescribes the implementation, I chose to use attoparsec instead. Not sure about the speed implications, but speed is not that important for me. The spec module also describes a parser. I did not have time to implement it, and am currently not planning to. But it would be nice if that was part of the package as well. I had hoped to be able to write a minimizer as well, but I'm not sure if it's possible to write a minimizer just on the token stream, maybe the full parser is needed for that. However, consecutive whitespace is collapsed so tokenizing and then serializing the file will in most cases lead to a smaller file. Hackage: http://hackage.haskell.org/package/css-syntax GitHub repo: https://github.com/wereHamster/haskell-css-syntax Spec: https://drafts.csswg.org/css-syntax

1 0

[ANN] base91
by Alvaro J. Genial 13 Aug '15

13 Aug '15

Howdy, I'd like to announce a first version of base91 <http://hackage.haskell.org/package/base91>, a Haskell package to enable the encoding and decoding of data in Base91 format, as documented in its specification <http://base91.sourceforge.net>. The main benefits of said scheme are a good reduction in overhead (from 31% up to 58%) when compared to Base64 due to the clever use of two printable ASCII characters (consuming 16 bits) to encode 13 arbitrary bits, as well as neither need for nor ambiguity over padding or alphabets. It includes support for... - Plain Strings (module Codec.Binary.Base91.String) - Data.ByteString (module Codec.Binary.Base91.ByteString) - Data.Text (module Codec.Binary.Base91.Text) - The latter two combined (module Codec.Binary.Base91.Efficient) - Data.ByteString.Lazy (module Codec.Binary.Base91.ByteString.Lazy) - Data.Text.Lazy (module Codec.Binary.Base91.Text.Lazy) - The latter two combined (module Codec.Binary.Base91.Efficient.Lazy) ...which are all just concretely typed versions of the generic implementation in Codec.Binary.Base91. I had fun exploring some of the latest GHC extensions, as evidenced by Codec.Binary.Base91.Control, which relies on a certain amount of type trickery to reconcile the incongruence between monomorphic containers and the standard type classes. Anyway, suggestions are very welcome. In particular, I'm interested in: 1. Whether the generic decode and encode signatures can be simplified or improved elsehow. 2. Whether there already exist classes similar in purpose to Applicative' and Foldable'. 3. Whether it makes sense to offer decode and encode variants that use lazy (left) folds--currently folding is always strict, even with lazy types. (Testing comes nearly free courtesy of QuickCheck and the identity property of decode . encode, plus a couple of concrete examples. Please open an issue or otherwise let me know if you find a bug.) Thank you, Alvaro <http://alva.ro>

4 5

HAL-10
by Pascal Wittmann 13 Aug '15

13 Aug '15

Hi there, I just wanted to ask whether I just missed this years HAL (Haskell in Halle/Leipzig) or if it was canceled this year. Cheers Pascal

2 1

Unique Ordered Types
by Silvio Frischknecht 12 Aug '15

12 Aug '15

Hi I'm experimenting with a unit system in haskell where users can add "base units". I want to reduce units after multiplication and bring it into a canonical form. The problem is what kind of types can the units have. 1) data UnitA data UnitB Problem: They can't be ordered so UnitA * UnitB can be compared to UnitB * UnitA, but I can't make a canonical form, which would make type inference a lot better. 2) type UnitA = Zero type UnitB = Suc Zero Problem: Now they can be ordered. But users can create conflicting "basic units" Silvio

4 6

Location Of Prelude.hs
by debdutk＠gnulinuxed.tk 12 Aug '15

12 Aug '15

Hi, I was reading the book "The Haskell Road to Logic, Math and Programming" and it refers to /usr/lib/hugs/libraries/Hugs/ as the probable location for Prelude.hs. I am currently using Elementary OS Luna (based of Ubuntu 12.04) and could not file the file at the specified location. Can anyone please tell me where to find it? _____________________ Yours Truly, Debdut Karmakar

4 5

ANN: stack-0.1.3.1
by Emanuel Borsboom 12 Aug '15

12 Aug '15

New release of stack, a build tool. This is a patch release to fix a bug in v0.1.3.0 <https://github.com/commercialhaskell/stack/releases/tag/v0.1.3.0>. See README <https://github.com/commercialhaskell/stack#how-to-install> for installation and upgrade instructions. Note: on Windows, this version does some trickery with code pages to work around issues with GHC’s output. If you run into any trouble, please report it (see issue #757 <https://github.com/commercialhaskell/stack/issues/757>). Bug fixes: - Ignore disabled executables #763 <https://github.com/commercialhaskell/stack/issues/763>

1 0

Combine `StateT` and `InputT` to maintain state on Ctrl-C interrupt
by haskell＠stefan-klinger.de 12 Aug '15

12 Aug '15

Hi, I'm stuck with maintaining a State in a Haskeline program that would survive an interrupt with Ctrl-C. The following is a MWE I have distilled out of a bigger project. It revolves around a simple (I guess) read-eval-print loop using Haskeline, and a stacked StateT to maintain a state. This MWE reads a line from the user, calculates its `length`, and adds the length to an Int forming the state. If the user types the special input "sleep" the program sleeps for 5 seconds, simulating a longer computation. Every time the user presses Ctrl-C * a running computation should be interrupted, or * when at the prompt, the current input should be cleared. * In any case, the state must be maintained! Unfortunately, Ctrl-C also clears the state. At first I thought I had stacked the `StateT` and `InputT` in the wrong order. But changing from `InputT (StateT Int IO) ()` to `StateT Int (InputT IO) ()` seems not to change anything (which really gives me the creeps). This message contains both versions (one commented out), they compile with $ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.10.1 $ ghc --make -Wall -outputdir tmp -o mwe StateMwe.lhs Example run, comments (`<--...`) added later: $ ./mwe type> arglschluargl Adding length of "arglschluargl" 13 type> lalala Adding length of "lalala" 19 type> <--no input, state unchanged Adding length of "" 19 type> sleep Sleeping 5 seconds... ^C <--Here I have hit C-c type> <--no input, state unchanged Adding length of "" 0 <--WRONG: that should be 19 Here we go: > import Control.Monad.State.Strict > import Control.Concurrent ( threadDelay ) > import System.Console.Haskeline > {- Version one: `StateT` inside `InputT` > main :: IO () > main = evalStateT (runInputT defaultSettings $ noesc repl) 0 This catches an interrupt via Ctrl-C and restarts the passed operation. > noesc :: MonadException m => InputT m a -> InputT m a > noesc w = withInterrupt $ let loop = handle (\Interrupt -> loop) w in loop The read-eval-print loop: EOF terminates, `sleep` delays, and any other input modifies the integer state. > repl :: InputT (StateT Int IO) () > repl = do x <- getInputLine "\ntype> " > case x of > Nothing -> return () > Just "sleep" > -> do outputStrLn "Sleeping 5 seconds..." > lift . lift . threadDelay $ 5 * 10^(6::Int) > outputStrLn "...not interrupted" > repl > Just t > -> do outputStrLn $ "Adding length of " ++ show t > lift $ modify (+ length t) > v <- lift get > outputStrLn $ show v > repl > -} > {- Version two: `InputT` inside `StateT` > main :: IO () > main = runInputT defaultSettings . noesc $ evalStateT repl 0 This catches an interrupt via Ctrl-C and restarts the passed operation. I suspect that I have to rearrange this to accommodate the modified stacking, but I could not come up with anything that compiles... > noesc :: MonadException m => InputT m a -> InputT m a > noesc w = withInterrupt $ let loop = handle (\Interrupt -> loop) w in loop As above, with `lift` in different places. To get a better understanding of what's going on, I do not want to use mtl's lift-to-the-right-monad magic (yet). > repl :: StateT Int (InputT IO) () > repl = do x <- lift $ getInputLine "\ntype> " > case x of > Nothing -> return () > Just "sleep" > -> do lift $ outputStrLn "Sleeping 5 seconds..." > lift . lift . threadDelay $ 5 * 10^(6::Int) > lift $ outputStrLn "...not interrupted" > repl > Just t > -> do lift . outputStrLn $ "Adding length of " ++ show t > modify (+ length t) > v <- get > lift . outputStrLn $ show v > repl > -} Any help would be welcome... Stefan -- http://stefan-klinger.de o/X /\/ \

3 9