August 2016 - Haskell-Cafe

The relationship between F-algebras and the Free Monad
by William Yager 13 Aug '16

13 Aug '16

Hello all, I recently read the article "Understanding F-algebras"[1], which goes over the usage of F-algebras for e.g. evaluating ASTs. This article goes over how 1. Data.Fix creates the initial F-algebra over a functor f. 2. We can express our AST as a non-recursive functor instead of a recursive type 3. We can express our evaluator as an Algebra (of the type `f a -> a`, where f is the type of our AST and `a` is the Algebra's carrier type, i.e. our result type) 4. We can express terms in our language as members of the type `Fix AST` (i.e. the initial F-algebra over our AST). 5. By using a catamorphism over our evaluator algebra, we can easily construct an efficient evaluator. As a brief example of these principles, see the following program (using DeriveFunctor): data AST a = Lit Int | Add a a deriving Functor -- data Fix f = Fix (f (Fix f)) -- defined in Data.Fix type AST' = Fix AST program :: AST' program = Fix $ Add (Fix $ Lit 5) (Fix $ Lit 4) alg :: AST Int -> Int alg (Lit i) = i alg (Add l r) = l + r eval :: AST' -> Int eval = Data.Fix.cata alg main = print $ eval program This is super cool! One thing that stood out to me is that there are a number of similarities here with the usage of the Free Monad. In particular, see "Why free monads matter" [2]. This article is doing basically the exact same thing. You express your AST as a non-recursive functor parametrized over the type of subterms. However, instead of making your terms of type `Fix AST`, they are of type `Free AST a`. Now, the recursive constructor for Free is almost identical to the constructor for Fix, except of course the additional type parameter `a`. However, both types are of the form `data T = R (f T)`. Free simply has the additional `Pure` constructor as well. So obviously, there is some sort of relationship here. However, I don't have a good enough grasp on these concepts for the relationship to make itself fully apparent. Some things I've noticed: Operations on `Fix AST` terminate because the AST type has leaf constructors without recursion. So a catamorphism over an evaluation algebra can plausibly terminate because eventually it will hit a leaf node and the evaluation will stop. On the other hand, operations on `Free AST a` can also terminate because you might run into a `Pure` constructor. The difference being that `Pure` is a part of the wrapper type (Free) and not the wrapped type (AST). A practical question I have is: Can we use the Free Monad to write AST terms using `do` notation (useful for DSLs) and then use the elegant catamorphism evaluator trick (or something similar) to evaluate our ASTs? Or does evaluating the Free Monad require something more general due to the Pure constructor? It looks like `Control.Monad.Free.iter` might be equivalent to `Data.Fix.cata`, but I'm not sure. It looks like a rough translation works in this case: data AST a = Add a a deriving Functor -- No more "Const" type AST' a = Free AST a program :: AST' Int program = Free $ Add (Pure 5) (Pure 4) alg :: AST Int -> Int alg (Add l r) = l + r eval :: AST' Int -> Int eval = Control.Monad.Free.iter alg main = print $ eval program So, intuitively, it seems like Free lets us do basically the same thing as Fix but with the evaluation result present as the last argument of the expression type. Sorry for being a bit rambly, and I may also be completely off base here, so correct me if I'm not making any sense. Cheers, Will [1] https://www.schoolofhaskell.com/user/bartosz/understanding-algebras [2] http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.ht…

1 0

(job) haskell software engineer for autopilot/simulation environment
by Greg Horn 13 Aug '16

13 Aug '16

We are a small, fast moving R&D group in Kitty Hawk <https://kittyhawk.aero/> writing autopilots in Haskell and code-generating to C. The ground station and simulation environment are written almost entirely in Haskell, and are mostly open-source. We are currently flight testing a few different novel vehicles. We're looking for an experienced software engineer familiar with simulation and control of dynamic systems, real-time systems, robotics, or similar. The role is initially to support and expand the existing simulation and control infrastructure, but will be flexible based on your interests and expertise. If this is interesting to you, please see the full description at: https://jobs.lever.co/kittyhawk.aero/89a6630b-4210-4a4a-89d8-936d458f6c8a?l… Best regards, Greg

1 0

Re: [Haskell-cafe] library for set of heterogeneous values?
by Anthony Clayden 13 Aug '16

13 Aug '16

> I don't know if they're at all suitable for your purposes, > but you should look (at least for inspiration) at both > vinyl and dependent-map. Thanks David, vinyl is a record 'solution', not a set-of-records repository Really there's now too many bewildering choices for records; representing the records is not the difficult part. dependent-map, and vault [Heinrich Apfelmus,thank you Sergei for the suggestion] seem to be (key, value) stores so I'm not seeing how I 'query'/filter the values (the whole records) if I don't already know the keys for those records. Contrast that with Data.Set [*], you could stream the contents to a list and filter. (Which would be horribly inefficient for my purposes.) [*] Data.Set seems to have been swallowed into the new collections library, which is not currently maintained :-( AntC

2 1

Need an example of new type constructor with zero data constructors
by James Brown 12 Aug '16

12 Aug '16

In the Haskell report 2010, a data declaration has the format of: <https://lh3.googleusercontent.com/-G-z92n-50B0/V63XKCCrJDI/AAAAAAAAAGA/w-Zd…> For a new type, there could be zero or more data constructors. What's the use case for a new type that has zero data constructor?

6 8

Hac φ: a Haskell Exchange in Philadelphia, Oct 21–23
by Richard Eisenberg 12 Aug '16

12 Aug '16

Hac Phi, a yearly weekend of Haskell in Philadelphia, will take place Oct. 21–23, 2016, at the University of Pennsylvania. Hac Phi is a gathering of hackers and Haskell enthusiasts. Come bring a project you’re working on or offer to help someone else on a project of theirs. Come give a talk if you’ve got something to share. Come to learn something new. What do we mean by a “Haskell Exchange”? Less pressurized than a hackathon, more informal than a conference, bigger than a meetup – Hac Phi is a weekend where academics, professionals, and hobbyists can all meet, mingle, hack on each others’ projects, and generally have a good time. (And it’s not to be confused with *the* Haskell eXchange, an entirely different event.) All the details are on [the wiki page](https://wiki.haskell.org/Hac_Phi); please [register online](https://goo.gl/forms/XXTxKFYAryVTjlgo2 <https://goo.gl/forms/XXTxKFYAryVTjlgo2>) if you’re coming. We hope to see you there! —The Hac φ team Antal Spector-Zabusky Kenny Foner

1 0

When you don't want to restrict the type of array...
by Christopher Howard 12 Aug '16

12 Aug '16

Hi. I recently learned how to use Haskell IArrays and MArrays, and they are quite convenient. I find myself often using some type of MArray for performance reasons, but also some IArray type for array data that is static in a set of computations. Then I started wanting to use arrays inside other kinds of data types, and so quickly ran into the question: what do you do if you want a data type to contain an array, but you don't know in advance what array type you'll be working with (immutable vs. mutible, boxed vs. unboxed). My exploration of this question led to discovering something called GADTs, which allowed me to do definitions like so data Surface a where ISurface :: IArray a e => (a Int Vertex) -> (a Int Face) -> Surface a MSurface :: MArray a e m => (a Int Vertex) -> (a Int Face) -> Surface a Am I heading down the right track here, or is there some better approach? -- https://qlfiles.net My PGP public key ID is 0x340EA95A (pgp.mit.edu)

2 1

Read lines of a file into a Vector
by Jake 11 Aug '16

11 Aug '16

I want to write a function that will read the contents of a file and return a Vector of its lines: readLines :: Handle -> IO (Vector String) I have an implementation that works but seems to naive and inefficient to me because it reads the entire file contents, *then *splits it into lines, and *then* converts it to a Vector from a list. readLines h = fromList . lines <$> hGetContents h I would like to a) use hGetLine and continue until I get an isEOFError and b) read directly into a Vector instead of a list. I started something using Data.Vector.unfoldr but I the presence of the IO monad around my String was causing issues I couldn't figure out how to solve. I'd also be curious to see how to do either one of these things separately and I assume they'd each help make my program more efficient on their own. Or, maybe my implementation is not as terrible as I thought because some laziness/fusion/optimization magic is happening behind the scenes? Thanks, Jake Waksbaum

3 2

[ANN] normalization-insensitive-2.0
by Patrick Pelletier 09 Aug '16

09 Aug '16

normalization-insensitive is identical to case-insensitive, except it is insensitive to Unicode normalization, rather than case. The module Data.Unicode.NormalizationInsensitive provides the NI type constructor which can be parameterized by a string-like type like: String, ByteString, Text, etc.. Comparisons of values of the resulting type will be insensitive to normalization. https://hackage.haskell.org/package/normalization-insensitive https://github.com/ppelleti/normalization-insensitive I created this to solve a problem I was running into comparing filenames on Mac OS X. Because Mac OS X converts all filenames to Normalization Form D, the filenames I read back from disk were different than the filenames I had written to disk. This package solved the problem very neatly. Under the hood, normalization-insensitive uses the unicode-transforms package, which Harendra Kumar announced a few days ago on haskell-cafe. This avoids having to pull in any heavyweight dependencies like ICU. Thanks to Bas van Dijk for writing case-insensitive, upon which normalization-insensitive is based. And thanks for Harendra Kumar for reviewing normalization-insensitive and providing feedback, as well as writing unicode-transforms. Although this is the first release of normalization-insensitive, the version number is 2.0 to avoid any confusion with the version numbers of case-insensitive. --Patrick

1 0

Re: [Haskell-cafe] Suggestions for an empirical master thesis
by Doug McIlroy 08 Aug '16

08 Aug '16

>The number of bugs would have to be normalized using the numbers of users of a project (maybe measured in number of downloads). Do you expect more bugs for frequently downloaded packages, or fewer downloads for packages with many bug reports or bug rate diminishing with downloads? It's a slippery topic. Doug

3 2

Re: [Haskell-cafe] Suggestions for an empirical master thesis
by Doug McIlroy 06 Aug '16

06 Aug '16

> >The number of bugs would have to be normalized using the numbers of users of a project (maybe measured in number of downloads).

1 0