News aggregator

How to run a tree transformer on the GPU?

Haskell on Reddit - Tue, 04/29/2014 - 1:16am

Suppose I have a simple recursive binary-tree like:

data T = Add T T | Mul T T | Sub T T | Div T T | Num Int

Now say I define a recursive function on that datatype:

eval :: T -> T eval (Add a b) = (eval a) + (eval b) eval (Mul a b) = (eval a) * (eval b) eval (Div a b) = (eval a) / (eval b) eval (Sub a b) = (eval a) - (eval b) eval (Num a) = a

If I am not wrong, algorithms like this one, that fold over trees without context, are embarrassingly parallel.

eval (Add (Add 1 2) (Mul 3 4))

Here, (Add 1 2) and (Mul 3 4) could be executed in parallel. My question, is: is there a way to take similar functions, and make them run in parallel, on the GPU?

submitted by SrPeixinho
[link] [42 comments]
Categories: Incoming News

Christopher Done: The Identity monad trick

Planet Haskell - Mon, 04/28/2014 - 6:00pm

Update: Got the link! The Trivial Monad. Thanks, John. Naturally, all interesting Haskell things eventually lead back to Dan Piponi.

I heard about this from John Wiegley a while ago, but every time I recall it, I can’t remember how it goes, so I thought I’d write it down for myself. I think there’s a paper about it, but I can’t find it. Hopefully I’m recalling it correctly.

The Identity monad trick: Let’s say I want to expose an API that lets you work with a data structure. I want you to be able to keep hold of that data structure and pass it back into my library, and I’ll give it back to you later and we can go back and forth.

But I don’t want you to actually give you the data structure freely so you can go and give it to your friends. So instead I force you into the Identity monad, via a newtype wrapper that only I can unpack.

newtype Secret a = Secret { unSecret :: Identity a } deriving (Monad,Functor,Applicative)

And I have some function exposing it like:

getSecret :: Foo -> Secret Text

Here, use that. What can you do with it? You can’t extract the value out, you can only compose it with more functor or monad stuff:

fmap (map T.toUpper) (getSecret foo)

Or:

do text <- getSecret foo if all T.isUpper text then return (T.reverse text) else return text

Note that the whole type of this expression is Secret Text. You still don’t have the secret, you’ve got a computation over it.

You’ve used the value, but it never escaped1 the actual Identity monad. It’s like I’m giving you the value, but I’m also not giving you the value.

  1. As always, there’s a difference between “secure against your own stupidity” and “secure against attackers.” For the former, this is satisfied.

    For the latter, bottom complicates it, so you should force it in the IO monad and catch any exceptions e.g.

    extract :: Secret a -> IO (Maybe a)

    This prevents people from using

    (v >>= \a -> error ("The value is " ++ show a))

    To try to get around it.

    unsafePerformIO and other non-standard Haskell can get around it, but if you’re defending against developers, you probably have control over the environment, so you can just white-list the imports and extensions and there’s nothing they can do. This is what tryhaskell (via mueval) does.

Categories: Offsite Blogs

When will hackage.haskell.org be upgraded to cabal 1.20?

Haskell on Reddit - Mon, 04/28/2014 - 4:19pm

With cabal 1.20 being available now--does anyone know when hackage.haskell.org will be upgraded?

submitted by tempo3000
[link] [1 comment]
Categories: Incoming News

[n00b]A General Question on Program Architecture: How do I Manipulate and Preserve Data Structures?

Haskell on Reddit - Mon, 04/28/2014 - 2:16pm

I'm a 2nd year computer science student and I've been studying Haskell for about 2 months. I'd say I have a good handle on how the language works and what it is capable of. I would definitely like to continue to work in Haskell after my studies have concluded.

I have encountered a mental roadblock though. How do I write programs that work in the real world, and not just in the limited GHCi sandbox? More specifically, when using a data structure like a tree or a table, how do I manipulate said structure while still preserving a consistent reference to it?

Here's an example of a tree I wrote to help illustrate my problem:

-- leaf-labelled trees of arbitrary data type -- a tree is either empty or is a node with an element and two sub-trees data BinTree a = Empty | Node a (BinTree a) (BinTree a) -- inductive case deriving (Eq, Ord, Show) --make a new tree newTree :: BinTree Int newTree = Empty --check if node is leaf isLeaf :: (Eq a) => BinTree a -> Bool isLeaf (Node _ c b) = if c == Empty && b == Empty then True else False isLeaf Empty = False --create a new leaf leaf :: a -> BinTree a leaf x = Node x Empty Empty --insert an element insert :: (Ord a) => a -> BinTree a -> BinTree a insert x Empty = leaf x insert x (Node v c1 c2) | x >= v = Node v c1 newc2 |otherwise = Node v newc1 c2 where newc2 = insert x c2 newc1 = insert x c1

With this code I can make an empty tree, add element to it, and with minimal work I could write code to traverse the tree as well. However, when actually running my code, how do I preserve changes to the tree?

For example, in GHCi:

let tree = newtree --make new tree Empty --result insert 5 tree -- add 5 to the tree Node 5 Empty Empty -- awesome, a tree with a non empty node is returned

Now here's my hangup. The only way I see to preserve the changes I've made to the tree would be to "save" the return value to a new "variable" (since function names cannot be reassigned). The original tree that I made can never be altered. If I cannot save my changes, how on earth do I move forward and write programs in haskell?

The only potential solutions I see here are:

  • Use IO to constantly read and write to a text file, thus preserving changes to data.
  • Monads? Do monads help here somehow? I actually have yet to use these, not clear on what's going on here.

Any feedback here would be great. I've read a lot into haskell, and a lot of high level topics are often covered in great detail, but none of the material I've read really seems to explicitly cover software engineering topics in functional programming. Am I missing something here?

submitted by Joel_gh719
[link] [11 comments]
Categories: Incoming News

What functionality can you cram into the typesystem?

Haskell on Reddit - Mon, 04/28/2014 - 12:30pm

As a beginner to Haskell, I am a little skeptical about the gains claimed by having strong types, as many of the bugs I see are not about wrong types, but rather a lack of anticipation of particular values.

Perhaps I am just not fully grasping the abilities of the type system. Can haskell handle scenarios like this?:

  • A string with no more than 3 'a' characters
  • An integer-like type which is only ever prime numbers
  • A binary tree, which must be balanced

If not, are there any languages which can do this?

submitted by DrBroccoli
[link] [24 comments]
Categories: Incoming News

My road to Haskell

Haskell on Reddit - Mon, 04/28/2014 - 8:15am
Categories: Incoming News

The printer Haskell deserves

Haskell on Reddit - Mon, 04/28/2014 - 6:21am
Categories: Incoming News

Yesod Web Framework: Disemboweling WAI (aka gutting out conduit)

Planet Haskell - Mon, 04/28/2014 - 4:51am

The Haskell Web Application Interface- or WAI- serves as a low-level interface between web applications and servers. In order to do this in a resource-efficient manner, it avoids lazy I/O and instead uses explicit streaming. The story of how it does that streaming has evolved over time: it initially used its own home-brewed streaming abstraction. Later, Gregory Collins convinced me to switch over to enumerator. In the 1.0 release, it switched to conduit, which was essentially designed for the very purpose of supporting WAI's use cases. While I'm very happy with conduit, baking conduit into WAI makes the barrier to using a different streaming framework (like pipes) higher.

So today, I'm proposing that we go all the way back to the beginning, and remove dependencies on external streaming frameworks from WAI, making it a completely universal web interface for Haskell.

I've been hesitant about doing this in the past due to two different reasons:

  1. Making this change makes it more difficult to write handlers and middleware for WAI.
  2. It's not really possible to get rid of a streaming abstraction entirely; instead, we end up just having a locally baked abstraction, which is less thoroughly tested than existing abstractions.

On the first point, most middlewares and handlers which modify request and response bodies are already maintained by the WAI team (and mostly by me personally), so I'm less concerned about pushing such a burden out onto the community. Thankfully, applications and frameworks can be completely insulated by this change by providing a wai-conduit adapter package.

Regarding the second point, I've recently had some experience with this: refactoring http-client out of http-conduit. It turned out to be relatively painless, though I did end up having to reimplement a number of combinators from conduit (especially in the test suite). Nonetheless, the codebase is about the same level of complexity, given the low-level nature of the http-client library, and there's been an overwhelmingly positive response to the splitting up of those two packages, so I want to try it out with WAI as well.

I've created a no-conduit branch in the WAI repo. Currently, I've converted the wai and warp repos over to be conduit-free (with a few helper functions stubbed out). And Warp passes its full test suite, which is rather promising.

The streaming interface is relatively simple. In order to consume a request body, you use the function:

requestBody :: Request -> IO ByteString

This function returns the next strict ByteString from the request body in the stream, or an empty ByteString if the body has been fully consumed. On the response side, you write an application with the type:

(Maybe Builder -> IO ()) -> IO ()

The argument function is used for emitting data to the user. If you provide a Just value, it sends the data in, and a Nothing value flushes the stream. (Currently, WAI uses the Flush data type from conduit for this purpose.)

The code is not yet ready to be released, but it is ready for some review and discussion. I'm hoping to hear community feedback, both from current users of WAI, and those who are considering using it (either directly in an application, or as part of a framework).

A separate breaking change that came up when working on this feature has to do with safe resource allocation and the definition of Application. In WAI 2.0, we introduced the function responseSourceBracket, which is a version of bracket that works for WAI applications. Internally to Warp (and every other WAI handler), we had to jump through some hoops to make sure async exceptions were all masked and restored properly. We also had to make our definition of ResponseSource a bit ugly to make this all possible.

Now with the move away from Sources, we have two choices: either perpetuate the strangeness in the ResponseStream and ResponseRaw constructor, or add bracket semantics to the entirety of a WAI application. In terms of code, I'm talking about replacing:

type Application = Request -> IO Response

with

type Application = Request -> (forall b. (Response -> IO b) -> IO b)

I've implemented this idea as well. It certainly makes the Warp codebase easier to follow, and allows for some slightly more powerful applications (e.g., acquiring a resource for use in some lazy I/O performed by ResponseBuilder). The downsides are:

  • Yet another breaking change.
  • It's harder to explain the intuition versus the dead simple Application we have now.
  • It will likely make middlewares significantly harder to write, though I'll admit that I haven't tried that yet.

When I discussed this change with Gabriel, he pointed out his Managed data type as a possible approach to make the signatures and usage slightly less scary. That would mean:

newtype Managed r = Managed { _bind :: forall x . (r -> IO x) -> IO x } type Application = Request -> Managed Response

Managed would be nice in that it provides a number of instances (including Monad), but it makes the WAI API a little bit denser to grok. I think I'm leaning against that direction, but wanted to raise this in the discussion as well.

Categories: Offsite Blogs