News aggregator

Daniil Frumin: Representable functors in Haskell

Planet Haskell - Sun, 02/02/2014 - 3:06am

I have finally managed to upload a (dry version) of a note about representable functors in Haskell. You can find it here: http://covariant.me/notes/rep-functors.html

Representable functors are functors that are isomorphic to $Hom(A, -)$ or $Hom(-, A)$ for some object $A$. In the note I give examples of some simple representable functors and prove that Maybe is not representable.


Tagged: category theory, functors, haskell, math
Categories: Offsite Blogs

wren ng thornton: This Week in Review

Planet Haskell - Sun, 02/02/2014 - 12:08am

Last friday I passed my qualifying examinations! So now, all I have left is a bunch of paperwork about that and then proposing, writing, and defending the dissertation itself. So, in about a year or so I'll be on the job market. And, much as I despise job hunting, I can't wait!

Since defending the quals I've been spending far too much time playing Persona 3 Portable. I've played P3FES, but P3P adds a female protagonist option which changes a bunch of the social interactions, so I've been playing through that side of things. Other than the heterosexual assumptions about the relationships, I've been loving it. More rpgs should have female protagonists. That's one of the reasons I've always loved FF6. Also a big part of why I found FF13 compelling. (Though, tbh: while Lightning is awesome as a protagonist, Vanille is definitely my favorite character :) And a big part of the powerfulness of Kreia as a character in KotOR2 stems from her interactions with the canonically-female protagonist.

Speaking of women. I've been presenting as female for a couple months now, and since I have no intention of stopping nor hiding that fact, I've decided to move T-Day forward. Basically, for those who haven't already switched over to the right pronouns etc: T-Day is today. I've sent emails to the department heads in order to get them to send out the "official" memo; so if you haven't gotten it yet, that should show up on monday or tuesday.

The next couple months are going to be hectic with paper writing. I'm hoping to get a paper on syntax-based sentiment-analysis using matrix-space semantics into one of the CL conferences with deadlines this March. No Haskell involved in that one, though I'll probably spend a few posts discussing the semantic model, which may be of interest to y'all. I'm also planning on getting the work from my first qual paper published; that paper was about Posta, a functional library for interactive/online/incremental tagging with HMMs. Here I'm planning to target journals rather than conferences, and it'll spread out over a few papers: one on the overall system (which I need to actually push up to Hackage), one on the higher-order anytime n-best extraction algorithm, and one on reformulating HMM algorithms in terms of foldl and scanl (this may be combined with the HO-AnB paper, length permitting). All of these would be targeting the linguistics audience. Using folds and scans is old-hat in functional programming; my particular goal with that paper is exposing linguists to the tools of FP and how they can be used to greatly simplify how we describe our algorithms. Once those are out of the way I might also see about writing up a functional pearl on the smoothing library I presented at AMMCS a few years back.



comments
Categories: Offsite Blogs

Castle: Permission denied

haskell-cafe - Sat, 02/01/2014 - 10:54pm
L.S., I am trying to install castle, but I get the following messages: Downloading castle-0.1.0.0... Configuring castle-0.1.0.0... realgcc.exe: ./specs: Permission denied What can I do about this? I am running Windows XP, Haskell Platform 2013.2.0.0 Regards, Henk-Jan van Tuyl
Categories: Offsite Discussion

Dan Piponi (sigfpe): Reinversion Revisited

Planet Haskell - Sat, 02/01/2014 - 7:53pm
Introduction

A while back I talked about the idea of reinversion of control using the continuation monad to wrest control back from an interface that only wants to call you, but doesn't want you to call them back. I want to return to that problem with a slightly different solution. The idea is that we build an interpreter for an imperative language that's an embedded Haskell DSL. You arrange that the DSL does the work of waiting to be called by the interface, but from the point of view of the user of the DSL it looks like you're calling the shots. To do this I'm going to pull together a bunch of techniques I've talked about before. This approach is largely an application of what apfelmus described here.


The code

We'll start with some administrative stuff before getting down to the real code:



> {-# LANGUAGE TemplateHaskell #-}



> import Control.Lens
> import Control.Monad
> import Control.Monad.Loops



We'll make our DSL an imperative wrapper around Gloss:



> import Graphics.Gloss.Interface.Pure.Game



We'll define a structure that can be used to represent the abstract syntax tree (AST) of our DSL. Our DSL will support the reading of inputs, adding pictures to the current picture, and clearing the screen.


First we'll need a wrapper that allows us to represent ordinary Haskell values in our DSL:



> data Basic a = Return a



Now we want an expression that represents events given to us by Gloss. Internally we'll represent this by a function that says what our program does if it's given an event. It says what our program does by returning another AST saying what happens when the input is received. (I've previously talked about these kinds of expression trees here).



> | Input (Event -> Basic a)



We have a command to render some graphics. It appends a new Picture to the current picture. Again, part of the AST muct be another AST saying what happens after the picture is rendered:



> | Render Picture (Basic a)



And lastly here's the AST for a clear screen command:



> | Cls (Basic a)



Our AST will form a monad. This will allow us to build ASTs using ordinary Haskell do-notation. This technique is what I described previously here.



> instance Monad Basic where
> return = Return
> Return a >>= f = f a
> Input handler >>= f = Input (\e -> handler e >>= f)
> Render p a >>= f = Render p (a >>= f)
> Cls a >>= f = Cls (a >>= f)



You can think of the expression x >>= f as x with the tree f a grafted in to replace any occurrence of Return a in it. This is exactly what Return a >>= f does. But applying >>= f to the other ASTs simply digs down "inside" the ASTs to find other occurrences of Return a.


It's convenient to uses lenses to view Gloss's game world:



> data World = World { _program :: Basic (), _picture :: Picture }
> $(makeLenses ''World)



And now we have some wrappers around the interpreter's commands. The return () provides the convenient place where we can graft subtrees into our AST.



> input = Input return
> render p = Render p (return ())
> cls = Cls (return ())



Now we can start coding. Here's a test to see if a Gloss event is a key down event:



> keydown (EventKey (Char key) Down _ _) = True
> keydown (EventKey (SpecialKey KeySpace) Down _ _) = True
> keydown _ = False



And now here's a complete program using our DSL. It's deliberately very imperative. It simply iterates over a nested pair of loops, collecting keystrokes and displaying them. It reads a lot like an ordinary program written in a language like Python or Basic:



> mainProgram = do
> render (Color white $ Scale 0.2 0.2 $ Text "Type some text")



> forM_ [780, 760..] $ \ypos -> do
> forM_ [0, 20..980] $ \xpos -> do



> event <- iterateUntil keydown $ input



> let key = case event of
> EventKey (Char key) Down _ _ -> key
> EventKey (SpecialKey KeySpace) Down _ _ -> ' '



> when (ypos == 780 && xpos == 0) $ cls
> render $ Color white $ Translate (xpos-500) (ypos-400) $ Scale 0.2 0.2 $ Text $ [key]



Here is where we launch everything, placing our program and starting Blank picture into the World.



> main = play (InWindow "Basic" (1000, 800) (10, 10))
> black
> 60
> (World mainProgram Blank)
> (^. picture)
> handleEvent
> (const id)



So now we need just one more ingredient, an actual interpreter for our AST. It's the event handler:



> handleEvent :: Event -> World -> World



The Return command is purely a place to graft in subtrees. It should never be interpreted.



> handleEvent _ (World (Return a) _) = error "error!"



After receiving some input, I want the interpreter to keep interpreting commands such as Cls that don't need any more input. I'm going to do this by using a null event EventMotion (0,0). But when an input really is desired, I want this null event to be ignored.



> handleEvent (EventMotion (0, 0)) state@(World (Input handler) _) = state



We render something by mappending it to the current picture stored in the World. But the rendering is carried out by the event handler. We update the state so that at the next event, the subtree of the AST is executed. This means that after updating the picture, the event still needs to be handed back to the event handler:



> handleEvent event state@(World (Render p cont) _) = state & (picture <>~ p) & (program .~ cont) & handleEvent event



Clearing the screen is similar:



> handleEvent event state@(World (Cls cont) _) = state & (picture .~ Blank) & (program .~ cont) & handleEvent event



And now we need to handle inputs. We do this by applying the "what happens when the input is received" function to the event. The result is put back in the state indicating that this is what we want to happen at the next event. So the interpreter doesn't stop here, waiting for the next event, the interpreter sends itself a null event.



> handleEvent event state@(World (Input handler) _) = state & (program .~ handler event) & handleEvent (EventMotion (0, 0))



And that's it!


There are many changes that can be made. We can easily add more commands and make the state more complex. But you might also notice that we create the AST only to tear it apart again in the interpreter. We can actually elide the AST creation, but that will eventually bring us back to something like what I originally posted. This shouldn't be a big surprise, I've already shown how any monad can be replaced with the continuation monad here. By the way, it's pretty easy to add a Fork command. You can replace the _program :: Basic() field with _program :: [Basic ()] and interpret this as a list of threads using a scheduler of your choice.


Acknowledgements

I was prompted to write this (a little late, I know) after reading this article and Tekmo's post on reddit. I think ultimately continuations may perform better than using ASTs. But sometimes it's nice to build an AST because they give you an object that can easily be reasoned about and manipulated by code. Much as I love trickery with continuations, I find ASTs are much easier to think about.


Postscript

My real motivation was that I was thinking about games. The rules of games are often given in imperative style: first player 1 does this. Then they do this. If this happens they do that. And then it's player two's turn. I wanted my Haskell code to reflect that style.


Update

Added 'null' event to keep interpreter going when it makes sense to do so, but there's no event pending.

Categories: Offsite Blogs

DSLs and heterogeous lists

haskell-cafe - Sat, 02/01/2014 - 5:55pm
Hi again, I have a game in which the user can create/write/read variables, using a small DSL. The type of the variable created can be whatever chooses the user, so I'm using existential types to store those variables in a heterogeneous list. This works fine, but the problem is that the "Typeable" class tag leaks into the DSL... The question is, how to get rid of it? This is the (simplified) DSL. With it you can read a variable stored in the game state (creation/writing is not shown). How can we get rid of the "Typeable a" in the ReadFirstVar constructor? This is the definition of a variable. The type is unknow, so I use existantial types. This game state. It holds the heterogenous list. The evaluation of "Exp" can be: As you can see, I'm obliged to cast the variable type to match it with the expression's type. Is that the right place to do it? Thanks!! Corentin _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://www.haskell.org/mailman/listinf
Categories: Offsite Discussion

Blog post (not really Haskell, but there are functors)

Haskell on Reddit - Sat, 02/01/2014 - 5:54pm

A while ago I posted about starting a math/programming blog. Some of you asked me to keep you updated, so although the newest post isn't about Haskell, it has some functors. New post! Part 2 should be coming in a day or two.

submitted by brianmannmath
[link] [comment]
Categories: Incoming News

Mark Jason Dominus: Why I like Java

Planet Haskell - Sat, 02/01/2014 - 4:47pm

My current employer uses an online quiz to pre-screen applicants for open positions. The first question on the quiz is a triviality, just to let the candidate get familiar with the submission and testing system. The question is to write a program that copies standard input to standard output. Candidates are allowed to answer the questions using whatever language they prefer.

Sometimes we get candidates who get a zero score on the test. When I see the report that they failed to answer even the trivial question, my first thought is that this should not reflect badly on the candidate. Clearly, the testing system itself is so hard to use that the candidate was unable to submit even a trivial program, and this is a failure of the testing system and not the candidate.

But it has happened more than once that when I look at the candidate's incomplete submissions I see that the problem, at least this time, is not necessarily in the testing system. There is another possible problem that had not even occurred to me. The candidate failed the trivial question because they tried to write the answer in Java.

I am reminded of Dijkstra's remark that the teaching of BASIC should be rated as a criminal offense. Seeing the hapless candidate get bowled over by a question that should be a mere formality makes me wonder if the same might be said of Java.

I'm not sure. It's possible that this is still a failure of the quiz. It's possible that the Java programmers have valuable skills that we could use, despite their inability to produce even a trivial working program in a short amount of time. I could be persuaded, but right now I have a doubtful feeling.

When you learn Perl, Python, Ruby, or Javascript, one of the things you learn is a body of technique for solving problems using hashes, which are an integral part of the language. When you learn Haskell, you similarly learn a body of technique for solving problems with lazy lists and monads. These kinds of powerful general-purpose tools are at the forefront of the language.

But when you learn Java, there aren't any powerful language features you can use to solve many problems. Instead, you spend your time learning a body of technique for solving problems in the language. Java has hashes, but if you are aware of them at all, they are just another piece of the immense Collections library, lost among the many other sorts of collections, and you have no particular reason to know about them or think about them. A good course of Java instruction might emphasize the more useful parts of the Collections, but since they're just another part of the library it may not be obvious that hashes are any more or less useful than, say, AbstractAction or zipOutputStream.

I was a professional Java programmer for three years (in a different organization), and I have meant for some time to write up my thoughts about it. I am often very bitter and sarcastic, and I willingly admit that I am relentlessly negative and disagreeable, so it can be hard to tell when I am in earnest about liking something. I once tried to write a complimentary article about Blosxom, which has generated my blog since 2006, and I completely failed; people thought I was being critical, and I had to write a followup article to clarify, and people still thought I was dissing Blosxom. Because this article about Java might be confused with sarcastic criticism, I must state clearly that everything in this article about Java is in earnest, and should be taken at face value. Including:

I really like Java

I am glad to have had the experience of programming in Java. I liked programming in Java mainly because I found it very relaxing. With a bad language, like say Fortran or csh, you struggle to do anything at all, and the language fights with you every step of the way forward. With a good language there is a different kind of struggle, to take advantage of the language's strengths, to get the maximum amount of functionality, and to achieve the clearest possible expression.

Java is neither a good nor a bad language. It is a mediocre language, and there is no struggle. In Haskell or even in Perl you are always worrying about whether you are doing something in the cleanest and the best way. In Java, you can forget about doing it in the cleanest or the best way, because that is impossible. Whatever you do, however hard you try, the code will come out mediocre, verbose, redundant, and bloated, and the only thing you can do is relax and keep turning the crank until the necessary amount of code has come out of the spout. If it takes ten times as much code as it would to program in Haskell, that is all right, because the IDE will generate half of it for you, and you are still being paid to write the other half.

So you turn the crank, draw your paycheck, and you don't have to worry about the fact that it takes at least twice as long and the design is awful. You can't solve any really hard design problems, but there is a book you can use to solve some of the medium-hard ones, and solving those involves cranking out a lot more Java code, for which you will also be paid. You are a coder, your job is to write code, and you write a lot of code, so you are doing your job and everyone is happy.

You will not produce anything really brilliant, but you will probably not produce anything too terrible either. The project might fail, but if it does you can probably put the blame somewhere else. After all, you produced 576 classes that contain 10,000 lines of Java code, all of it seemingly essential, so you were doing your job. And nobody can glare at you and demand to know why you used 576 classes when you should have used 50, because in Java doing it with only 50 classes is probably impossible.

(Different languages have different failure modes. With Perl, the project might fail because you designed and implemented a pile of shit, but there is a clever workaround for any problem, so you might be able to keep it going long enough to hand it off to someone else, and then when it fails it will be their fault, not yours. With Haskell someone probably should have been fired in the first month for choosing to do it in Haskell.)

So yes, I enjoyed programming in Java, and being relieved of the responsibility for producing a quality product. It was pleasant to not have to worry about whether I was doing a good job, or whether I might be writing something hard to understand or to maintain. The code was ridiculously verbose, of course, but that was not my fault. It was all out of my hands.

So I like Java. But it is not a language I would choose for answering test questions, unless maybe the grade was proportional to the number of lines of code written. On the test, you need to finish quickly, so you need to optimize for brevity and expressiveness. Java is many things, but it is neither brief nor expressive.

When I see that some hapless job candidate struggled for 15 minutes and 14 seconds to write a Java program for copying standard input to standard output, and finally gave up, without even getting to the real questions, it makes me sad that their education, which was probably expensive, has not equipped them with with better tools or to do something other than grind out Java code.

Categories: Offsite Blogs

Having fun with Haskell, Anyone got any clever solutions!

Haskell on Reddit - Sat, 02/01/2014 - 3:07pm

imagine a new version of Hopscotch that is a combination of a hopping game with a brain teaser. These are the simple rules:

  1. The squares are laid in a straight line.
  2. The squares have a marker on it that are worth a number of points between 1 and 10.
  3. As you hop along, you can pick up the marker in each square that you hop in.
  4. In the end, your score is the total number of points on the markers you've picked up.

The fun part is that you can't hop in all the squares. You start in the first square (and collect the marker on that square) all the time. Every jump after must take you to a square that is either 2 or 3 squares away from your current position past your current square.

Basically, each jump must skip either 1 or 2 squares.

When you get to either the last square or the next-to-last square in the course, you jump off the end and you're done.

Ps. You can't hop backwards.

ex - Prelude> hopscotch [7,4,5,9,6,1,2,3] ([7,5,6,3],21)

submitted by ProgramHaskell
[link] [25 comments]
Categories: Incoming News

Mixing own and derived instances with GenericDeriving Mechanism

haskell-cafe - Sat, 02/01/2014 - 2:11pm
Dear Pedro, Cafe, Thanks again for helping me out last December. I have been playing a bit more with deriving show and now ran into an interesting problem mixing my own instances with derived instances. Hope you can enlighten me there! > {-# LANGUAGE DeriveGeneric #-} > module Test where > import GHC.Generics > import Generics.Deriving.Show The Generic Deriving Mechanism adds the keyword 'default' to class definitions. With this keyword we can define a type-generic definition of that method when not given. For example, if we define our own MyData type, we can derive the GShow methods: > data MyData = MyData MyFancyType deriving Generic > instance GShow MyData We can also still give our own definition, for example if we want values of the MyFancyType to always be shown as the same string: > data MyFancyType = MyFancy1 | MyFancy2 deriving Generic > instance GShow MyFancyType where > gshow _ = "Fancy!" There is something strange here though: when we use gshow directly on a MyFancyType val
Categories: Offsite Discussion

(Question) DSLs and heterogeneous lists

Haskell on Reddit - Sat, 02/01/2014 - 9:57am

I have a game in which the user can create/write/read variables, using a small DSL. The type of the variables created can be whatever chooses the user, so I'm using existential types to store those variables in a heterogeneous list. This works fine, but the problem is that the "Typeable" class tag leaks into the DSL... The question is, how to get rid of it?

> This is literate Haskell > {-# LANGUAGE GADTs, ScopedTypeVariables #-} > module DSLClass where > import Control.Monad > import Control.Monad.State > import Data.Typeable

This is the (simplified) DSL. With it you can read a variable stored in the game state (creation/writing is not shown). How can we get rid of the "Typeable a" in the ReadFirstVar constructor?

> -- first type parameter is used to track effects > data Exp a where > ReadFirstVar :: (Typeable a) => Exp a <----- Ugly > Return :: a -> Exp a > Bind :: Exp a -> (a -> Exp b) -> Exp b

This is the definition of a variable. The type is unknow, so I use existantial types.

> data Var = forall a . (Typeable a) => Var { v :: a}

This game state. It holds the heterogenous list.

> data Game = Game { variables :: [Var]}

The evaluation of "Exp" can be:

> eval :: Exp a -> State Game a > eval ReadFirstVar = do > (Game ((Var v):vs)) <- get > case cast v of > Just val -> return val > Nothing -> error "no cast" > eval (Bind exp f) = do > a <- eval exp > eval (f a)

As you can see, I'm obliged to cast the variable type to match it with the expression's type. Is that the right place to do it?

Thanks!!

submitted by kaukau
[link] [10 comments]
Categories: Incoming News

Yesod Web Framework: PostgreSQL, UTCTime, and WITHOUT TIME ZONE

Planet Haskell - Sat, 02/01/2014 - 8:40am

I've just added a Wiki page describing the situation in PostgreSQL databases regarding the schema type used for UTCTime. This is a question that seems to come up every so often and, since I just wrote a user a rather lengthy explanation of the problem, decided it was time to set up a canonical location for the information. I've copied the full content of the Wiki page below for ease of viewing.

My question is: have I missed some use case with this explanation?

A question which comes up quite a bit is why persistent-postgresql stores UTCTime values in the database as TIMESTAMP WITHOUT TIME ZONE instead of WITH TIME ZONE. There are two datatypes in Haskell, and two in PostgreSQL, relevant to this discussion:

  • Haskell
    • UTCTime: An exact moment in time, in the UTC timezone.
    • ZonedTime: A UTCTime plus a timezone.
  • PostgreSQL
    • WITHOUT TIME ZONE: A time stamp, which could be in any time zone.
    • WITH TIME ZONE: An exact moment in time, with a given time zone.

It's clear from this that ZonedTime and WITH TIME ZONE line up perfectly. The problem is that there's a small mismatch between UTCTime and WITHOUT. The latter could imply any timezone, which is quite problematic. When Persistent uses this SQL type, it guarantees that all stored timestamps are in UTC time, and therefore does not run into any issues of mismatched timezones.

However, why not get the extra safety of being explicit about the timezone selection in the database? The problem comes down to what Persistent should do in the case of a value in a non-UTC timezone. There are essentially two options:

  1. Raise an exception about unexpected data. This is suboptimal, since we would like to avoid runtime errors like this whenever possible, and instead rely on the type system + SQL schema to keep things safe.
  2. Simply discard the timezone information. The problem here is that roundtripping will no longer work: reading a value, dropping the timezone, and writing back to the database would force a conversion to the UTC timezone, which may not be what a user wants.

So in your application, what should you do? Here's my recommendation:

  • If your database is only being accessed from Persistent, using UTCTime and WITHOUT TIME ZONE is perfectly safe, and is a simpler option.
    • Unless, of course, you actually want to store timezone information, in which case you should use ZonedTime!
  • If you're dealing with an existing database, or publishing data that other applications will need to see, always use ZonedTime. Inside your application, you can trivially converted to a UTCTime instead. But this will force you to be aware of any data loss you may be performing, and of any roundtripping issues you may be introducing to your database.
Categories: Offsite Blogs

davean/waldo · GitHub

del.icio.us/haskell - Sat, 02/01/2014 - 8:34am
Categories: Offsite Blogs

Trolling #haskell

del.icio.us/haskell - Sat, 02/01/2014 - 7:13am
Categories: Offsite Blogs