I haven’t done a single web overview in 2013. It’s time to fix that since in the last few weeks I came across a couple of interesting online resources that I’d like to share:
- Fun with type functions (2011) – Simon PJ’s presentation of the tutorial paper with the same title. Covers associated data types and type families (see “Associated Types With Class” for an in-depth presentation) + some stuff found in Data Parallel Haskell (read “Data Parallel Haskell: a status report” for more details). The whole presentation feels like a teaser as it ends quite quickly and skips some really interesting examples found in the paper.
- Types a la Milner (2012) by Benjamin C. Pierce (he’s the author of the book about types “Types and Programming Languages”). The talk covers a bit of programming languages history, type systems in general (“well-typed programs don’t go wrong”), type inference in the presence of polymorphism and using types to manage security of personal information. I found the type inference and historical parts very interesting.
- The trouble with types (2013) by Martin Odersky (creator of Scala). Talk covers the role of types in programming, presents the spectrum of static type systems and then focuses on innovations in the type system of Scala.
- I also found an interesting blog hosted on GitHub. Despite only 10 posts the blog has lot’s of stuff on practical type level programming in Haskell. Highly recommended.
I've recently been working on some higher level analysis utilities based on top of conduit. A major component of this work is performing high-performance numerical calculations on large streams of data. So I was particularly intriguied when I saw a StackOverflow question that touched on the same points. I'd like to elaborate on my answer to that question, and demonstrate a possible addition to the conduit library.
The issue at play in that question is the desire to tally up the frequency of each octet in a stream of data. If you look through the answers, it quickly becomes apparent that using some kind of a mutable packed data structure (either Vector or Array) provides drastically better performance than immutable data structures. For our purposes, let's stick with the vector library, though the discussion here applies equally well to array.
The actions we need to perform are very straight-forward: read in the entirety of the data from some source (let's say standard input), and perform a mutating action for each and every octet that we receieve. We could read the entire stream of data using lazy I/O, but as readers of this blog are likely aware, I'd rather avoid lazy I/O when possible. So in my answer, I used conduit to read in the stream of data. The answer looks like this:import Control.Monad.Trans.Class (lift) import Data.ByteString (ByteString) import Data.Conduit (Consumer, ($$)) import qualified Data.Conduit.Binary as CB import qualified Data.Vector.Unboxed as V import qualified Data.Vector.Unboxed.Mutable as VM import System.IO (stdin) freqSink :: Consumer ByteString IO (V.Vector Int) freqSink = do freq <- lift $ VM.replicate 256 0 CB.mapM_ $ \w -> do let index = fromIntegral w oldCount <- VM.read freq index VM.write freq index (oldCount + 1) lift $ V.freeze freq main :: IO () main = (CB.sourceHandle stdin $$ freqSink) >>= print
We now have a reusable freqSink component that will consume a stream of ByteStrings to produce a Vector Int of the frequencies. The Sink creates a new mutable vector to hold the frequency values, maps over all the input octets, and for each octet updates the mutable vector. Finally, it freezes the mutable vector into an immutable one and returns it.
I like almost everything about this, except for two characters: IO. Our freqSink function sets the base monad to be IO, implying that freqSink may perform actions that have an impact on the outside world. However, we know that this isn't the case: by analyzing the code, we see that all of the mutating changes are contained within the little world that freqSink creates for itself. In other words, this function is referentially transparent, but the type signature is saying otherwise.
Fortunately, Haskell already has the perfect solution for this kind of a problem: the ST monad. All we need to do is swap IO for ST s and freqSink will be properly annotated as being referentially transparent. But when we make this change, we get the following error message:Couldn't match type `ST s0' with `IO'
The problem is that, while freqSink is refentially transparent, sourceHandle is not. Since the source is capable of performing arbitrary IO, it has to live in the IO base monad, and since the two components live in the same processing pipeline, freqSink must match that base monad as well. While this all works, it's still quite disappointing.
But perhaps we can have our cake and eat it too. We want freqSink's type signature to be refentially transparent, which means it needs to live in ST. What we need is some way to turn an ST-based Sink into an IO-based Sink. And there's a function that let's us do just that: unsafeSTToIO. This ends up looking like:import Control.Monad.Morph (hoist) import Control.Monad.ST (ST) import Control.Monad.ST.Unsafe (unsafeSTToIO) import Control.Monad.Trans.Class (lift) import Data.ByteString (ByteString) import Data.Conduit (Consumer, ($$)) import qualified Data.Conduit.Binary as CB import qualified Data.Vector.Unboxed as V import qualified Data.Vector.Unboxed.Mutable as VM import System.IO (stdin) freqSink :: Consumer ByteString (ST s) (V.Vector Int) freqSink = do freq <- lift $ VM.replicate 256 0 CB.mapM_ $ \w -> do let index = fromIntegral w oldCount <- VM.read freq index VM.write freq index (oldCount + 1) lift $ V.freeze freq main :: IO () main = (CB.sourceHandle stdin $$ hoist unsafeSTToIO freqSink) >>= print
This once again works, and freqSink's type signature now indicates that it is referentially transparent. However, we've put two heavy burdens on users of our freqSink function:
- They need to know about hoist and understand how to use it.
- They need to pull in an unsafe function and know in which circumstances it's safe to use it.
What we really want is to provide a general purpose function which is completely safe. We want to contain the concept of "I can safely swap out the base monad of this Conduit with some other base monad." So I've just pushed a new commit to conduit adding the conduitSwapBase helper function (name up for debate). Let's start by seeing how it solves our present problem:import Control.Monad.ST (ST) import Control.Monad.Trans.Class (lift) import Data.ByteString (ByteString) import Data.Conduit (Consumer, ($$)) import qualified Data.Conduit.Binary as CB import Data.Conduit.Util (conduitSwapBase) import qualified Data.Vector.Unboxed as V import qualified Data.Vector.Unboxed.Mutable as VM import System.IO (stdin) freqSinkST :: Consumer ByteString (ST s) (V.Vector Int) freqSinkST = do freq <- lift $ VM.replicate 256 0 CB.mapM_ $ \w -> do let index = fromIntegral w oldCount <- VM.read freq index VM.write freq index (oldCount + 1) lift $ V.freeze freq freqSink :: Monad m => Consumer ByteString m (V.Vector Int) freqSink = conduitSwapBase freqSinkST main :: IO () main = (CB.sourceHandle stdin $$ freqSink) >>= print
I renamed the previous function to freqSinkST, leaving its type exactly as it was. In addition, we now have a new freqSink, which can live in any base monad. The type signature makes it completely clear that this function is referentially transparent. And all we needed to do was use conduitSwapBase to perform this conversion.
Once that conversion is performed, we can easily combine freqSink with our IO-based sourceHandle. Or for that matter, it could be combined with a completely pure source, or a source living in the Maybe monad.
As it stands right now, conduitSwapBase will allow the following base transformations to be applied:
- ST can be converted to ~~any other monad~~. EDIT See update below.
- Identity can be converted to any other monad.
- IO can be converted to any instance of MonadIO.
- For many transformers (all instances of MonadTransControl actually), if the base monad m1 can be converted to m2, then the transformer t m1 can be converted to t m2.
This addition allows us to keep more type safety in our codebase, while still allowing safe interleaving of IO actions with pure code. I'm happy with the addition so far, I'm curious to hear further ideas from the community.
UPDATE: As pointed out on Reddit, a backtracking base monad can break refential transparency for ST. I've pushed a new commit that constrains the types of monads that can be converted to. In particular, it works for monads which are processed in a linear/non branching manner. This includes Identity, IO and Maybe, and transformers like ReaderT and ErrorT.
I'm currently calling this concept MonadLinear, but I have a strong feeling that there's a better abstraction already in existence.
I recently wrote a paper for the 26th International Conference on Computer Aided Verification (CAV’14), Vienna, Austria. The paper is titled “Verifying weight biased leftist heaps using dependent types”. In this paper I have taken a weight biased leftist heap data structure presented by Okasaki in “Purely Functional Data Structures” and created its Agda implementation, which uses dependent types to statically guarantee that rank and priority invariants are maintained. My verification is based on techniques demonstrated by Altenkirch, McKinna and McBride in “Why Dependent Types Matter” but my focus is on things that were left out in that paper. In the end my paper is an intermediate level tutorial on verification in Agda but also a case study of a purely functional data structure implemented in a dependently typed setting. Worth noting is the fact that despite title of Okasaki’s book his implementation is not purely functional as it uses exceptions to deal with edge cases like taking the smallest element from an empty heap.
Draft version of the paper can be downloaded here. It comes with companion source code that contains a thorough discussion of concepts presented in the paper as well as others that didn’t make it into publication due to space limitations. Companion code is available at GitHub (tag “blog-post-draft-release” points to today’s version). The paper is mostly finished. It should only receive small corrections and spelling fixes. However, if you have any suggestions or comments please share them with me – submission deadline is in three weeks so there is still time to include them.
What's it for? I know the Functor class is for computations with a context, and Contravariant is similar in the type signature. Is it possible to use Contravariant with Applicative and Monad?submitted by danmwilson
[link] [14 comments]
Recently, a large number of the dependencies for Yesod (aeson, fast-logger, warp, attoparsec, etc) have gone through major version bumps. At the same time, a number of other dependencies of Yesod have not relaxed their version bounds for the most recent versions of their dependencies. This situation leads to a lot of confusion for cabal trying to figure out a coherent installation path.
This is precisely the situation for which the yesod-platform situation was designed. If you are having trouble getting Yesod installed, please try running cabal install yesod-platform instead of yesod. (In fact, unless you have reason to do otherwise, I highly recommend always doing this.) If you have an existing project with its own set of dependencies, go into that directory and run cabal install . yesod-platform, which will attempt to choose a version of yesod-platform with dependencies that fit your constraints. If you use some kind of sandboxing, modify the above commands as necessary.
And let me take this opportunity to mention: if you're trying to build your code on a stable platform, you should make sure that you pin down the versions of all of your dependencies. Greg Weber wrote a great blog post explaining a technique that should fit into most people's standard build processes. Using the Stackage pinned version set will also guarantee builds that are coherent. And of course, building on FP Haskell Center guarantees stable and tested versions of packages which will be maintained.
UPDATE There are two important command line options I should have mentioned. If you're running into dependency hell, try appending the following: --max-backjumps=-1 --reorder-goals.