News aggregator

Chaining modifications using (>>>)

haskell-cafe - Sat, 09/20/2014 - 2:14am
Hello all, I've been playing with Data.Graph.Inductive, which provides functions to modify a graph. I take these functions and build something more complex from them. To do so, I have to apply several such modifications one after the other. I can write this using ($) or (.), but I didn't like to write things backwards (last function to apply comes first), so I use (>>>) from the Arrows module to chain functions Graph -> Graph (aka GraphTransforms) and my complex function looks like f >>> g >>> h. To actually build a Graph I have to apply my function to some Graph (often "empty"). This works okay as long as the inidividual functions f,g,h do not need access to the graph. However, there is one function where I use "pre" (predecessors) and "suc" (succerssors), which need the Graph as a parameter. groupNodes :: DynGraph gr => (Label,[Node]) -> GraphTransform gr pl groupNodes (lbl,ids) gr = let id = head $ newNodes 1 gr oldEdgesTo = [(toOld, old) | old <- ids, toOld <- pre gr old] -- <== he
Categories: Offsite Discussion

Eric Kidd: Rust lifetimes: Getting away with things that would be reckless in C++

Planet Haskell - Fri, 09/19/2014 - 9:07pm

Over the years, I've learned to be cautious with C++ pointers. In particular, I'm always very careful about who owns a given pointer, and who's in charge of calling delete on it. But my caution often forces me to write deliberately inefficient functions. For example:

vector<string> tokenize_string(const string &text);

Here, we have a large string text, and we want to split it into a vector of tokens. This function is nice and safe, but it allocates one string for every token in the input. Now, if we were feeling reckless, we could avoid these allocations by returning a vector of pointers into text:

vector<pair<const char *,const char *>> tokenize_string2(const string &text);

In this version, each token is represented by two pointers into text: One pointing to the first character, and one pointing just beyond the last character.1 But this can go horribly wrong:

// Disaster strikes! auto v = tokenize_string2(get_input_string()); munge(v);

Why does this fail? The function get_input_string returns a temporary string, and tokenize_string2 builds an array of pointers into that string. Unfortunately, the temporary string only lives until the end of the current expression, and then the underlying memory is released. And so all our pointers in v now point into oblivion—and our program just wound up getting featured in a CERT advisory. So personally, I'm going to prefer the inefficient tokenize_string function almost every time.

Rust lifetimes to the rescue!

Going back to our original design, let's declare a type Token. Each token is either a Word or an Other, and each token contains pointers into a pre-existing string. In Rust, we can declare this as follows:

#[deriving(Show, PartialEq)] enum Token<'a> { Word(&'a str), Other(&'a str) }

Read more…

Categories: Offsite Blogs

Christopher Done: hindent: A Haskell indenter

Planet Haskell - Fri, 09/19/2014 - 6:00pm
A question of style

In this post I’m going to use the word “style” to refer to the way code is printed in concrete terms. No changes in the code that would yield a different syntax tree are considered “style” here.

What’s the deal with code style?

Code style is important! If you’re a professional Haskell programmer, you’re working with Haskell code all day. The following things are affected by the style used:

  • How easily it can be manipulated with regular editors: the more code is laid out in a way that prevents you from readily using your normal editor functions, the less efficient you are.
  • How well general tooling works with it: do diff and things like that work well?
  • How easily you can absorb the structure: do you have to spend time hunting around for the start and end of syntactical nodes? Can’t see the tree for the forest?
  • How quickly you can write it: can you just write code or do you have to spend time thinking about how it’s going to be laid out before writing, or editing the layout afterwards?
  • How aesthetically offended you are1: does the code you’re looking at assault your sense of beauty?

Code style is important! Let’s have a code style discussion. I propose to solve it with tooling.

Is this really an issue, though?

Okay, so I’m one guy with a bee in his bonnet. Let’s do a quick Google and see what others are saying in this StackOverflow question:

Could someone provide a link to a good coding standard for Haskell? I’ve found this and this, but they are far from comprehensive.

The following points refer to style:

  • Format your code so it fits in 80 columns. (Advanced users may prefer 87 or 88; beyond that is pushing it.)
  • Put spaces around infix operators. Put a space following each comma in a tuple literal.
  • Prefer a space between a function and its argument, even if the argument is parenthesized.
  • Use line breaks carefully. Line breaks can increase readability, but there is a trade-off: Your editor may display only 40–50 lines at once. If you need to read and understand a large function all at once, you mustn’t overuse line breaks.
  • When possible, align – lines, = signs, and even parentheses and commas that occur in adjacent lines.

Even the Haskell community is not immune to long, protracted debates about tabs vs spaces. That reddit submission has zero points. That means it’s very controversial. The submission also has 117 comments. That means people are very vocal about this topic. That’s because bike-shedding is inversely proportional to the triviality of the debated thing. We know that.

Nevertheless, style is important enough to be discussed.

So let’s formalise a standard style

That’s a simplification. There are many style guides:

These are just public ones. In-house styles are also common, for a particular company. It’s not practical to force everyone into one single style. It’s a well-worn topic in the C world.

Okay, but is this a problem tooling even needs to solve?

There is precedent for other tooling based on style:

Everyone has their own style

So then let’s make a tool with a select number of styles, you might say. The problem is that people don’t even use the standards that exist out there. They used slightly varying versions. Ask any Haskeller what style they use, and they will say “mostly like X, but with some differences.”

For example What are some good style guides for writing Haskell code?2

I use a very similar style, with a few modifications. […] Perhaps I should write out my own style guide at some point, especially as I’ve become pretty set in my style lately.

And Good Haskell Coding Style3:

My Personal Pet Peeves

For the most part the style guides that I have added above (and the tools provided) mirror my own style guide (or perhaps my guide mirrors them). However, there is one item of style that particularly annoys me on a regular basis. […]

Can’t we just use structured editors?

Some more optimistic folk out there might suggest, perhaps, we should just throw away text files and go straight for structured code databases. Put all this formatting nonsense behind us. Layout is just a stylesheet! It’s not data to be stored in a file!

Maybe so. But nobody is using structured editors yet.

A practical way forward

Taking all of the above into consideration, here is my approach at the problem. The hindent library and program. Styled on GNU indent, the intention is that you simply run the program on some source code and it reformats it.

$ hindent hindent: arguments: --style [fundamental|chris-done|johan-tibell]

hindent has the concept of styles built in. There is a type for it:

data Style = forall s. Style {styleName :: !Text ,styleAuthor :: !Text ,styleDescription :: !Text ,styleInitialState :: !s ,styleExtenders :: ![Extender s] ,styleDefConfig :: !Config }

It contains authorship metadata. It holds an initial state which can be used during printing. Most importantly, it has a list of extenders. Means to extend the printer and change its behaviour on a node-type-specific basis.

Take a normal pretty printing approach. It’s usually something like:

class Pretty a where pretty :: a -> String

Then for all the types in the AST we implement an instance of Pretty.

The limitation here is that we can’t, as a user of the library, decide to print one particular node type differently.

Instead, here’s a new class:

class (Annotated ast,Typeable ast) => Pretty ast where prettyInternal :: ast NodeInfo -> Printer ()

(It runs in a Printer type to store some state about the current column and indentation level, things like that.)

Now, we implement the prettyInternal method for all our types. But when implementing instances, we never use the prettyInternal method directly. Instead, we use another function, pretty, which can be considered the main “API” for printing, like before. Here’s the type:

pretty :: (Pretty ast) => ast NodeInfo -> Printer ()

We’ll look at its implementation in a moment. Here is an example instance of Pretty:

instance Pretty ClassDecl where prettyInternal x = case x of ClsTyDef _ this that -> do write "type " pretty this write " = " pretty that …

See how pretty this and pretty that are used for recursing instead of prettyInternal? This approach is used for all instances.

Now let’s see what that affords us:

pretty :: (Pretty ast) => ast NodeInfo -> Printer () pretty a = do st <- get case st of PrintState{psExtenders = es,psUserState = s} -> do case listToMaybe (mapMaybe (makePrinter s) es) of Just m -> m Nothing -> prettyNoExt a printComments a where makePrinter s (Extender f) = case cast a of Just v -> Just (f s v) Nothing -> Nothing makePrinter s (CatchAll f) = (f s a)

In this function, we’re grabbing our (mentioned earlier) list of [Extender s] values from psExtenders and then looking up to see if any of the types match. To clarify, here is the Extender type:

data Extender s where Extender :: forall s a. (Typeable a) => (s -> a -> Printer ()) -> Extender s CatchAll :: forall s. (forall a. Typeable a => s -> a -> Maybe (Printer ())) -> Extender s

Both constructors are rank-n. Both accept the current state as an argument and the current node. The Extender constructor is Prismesque. It’s existential, and lets you say “I want things of this type”. The CatchAll will just accept anything.

All that adds up to me being able to do something like this. Here’s a demo style:

demo = Style {styleName = "demo" ,styleAuthor = "Chris Done" ,styleDescription = "Demo for hindent." ,styleInitialState = () ,styleExtenders = [Extender (\_ x -> case x of InfixApp _ a op b -> do pretty a pretty op pretty b _ -> prettyNoExt x)] ,styleDefConfig = def}

(The prettyNoExt is a publicly exposed version of the (private) method prettyInternal.)

Now let’s test the fundamental style versus our demo style:

λ> test fundamental "x = foo (a * b) + what" x = foo (a * b) + what λ> test demo "x = foo (a * b) + what" x = foo (a*b)+what

Viola! We’ve configured how to pretty print infix operators in a few lines of code.

In practice, there are three styles. Here’s a larger example:

foo = do print "OK, go"; foo (foo bar) -- Yep. (if bar then bob else pif) (case mu {- cool -} zot of Just x -> return (); Nothing -> do putStrLn "yay"; return (1,2)) bill -- Etc where potato Cakes {} = 2 * x foo * bar / 5

Fundamental style:

foo = do print "OK, go" foo (foo bar) (if bar then bob else pif) (case mu {- cool -} zot of Just x -> return () Nothing -> do putStrLn "yay" return (1,2)) bill -- Etc where potato Cakes{} = 2 * x foo * bar / 5

Johan Tibell’s style (which I’ve only started implementing, there’re some things I need to clarify):

foo = do print "OK, go" foo (foo bar) (if bar then bob else pif) (case mu {- cool -} zot of Just x -> return () Nothing -> do putStrLn "yay" return (1, 2)) bill -- Etc where potato Cakes{} = 2 * x foo * bar / 5

My style (pretty much complete):


The styles are part of the module hierarchy of the package.

Write your own style!

I welcome anyone to write their own style. All styles are based upon the fundamental style, which should never change, by extending it. You can base yours off of another style, or start from scratch. While you can keep your style locally, like your XMonad configuration, it’s encouraged to contribute your style as a module.

My style and Johan’s are quite different. But yours may be similar with small tweaks. Another distinctly different style is Simon Peyton Jones’s with explicit braces. This is a style you can implement if you want it.

See the contributing section of the README for more info.

Preserving meaning

A recommendation is to preserve the meaning of the code. Don’t make AST changes. Like removing parentheses, changing $ into parens, moving lets into wheres, etc. You can do it, but the results might surprise you.

Editing advantages

Having implemented Emacs support, I have been using this for a few weeks on my own code. It’s amazing. I’ve all but stopped manually making style changes. I just write code and then hit C-c i and it almost always does exactly what I want.

It can’t always do what I want. It has simple, predictable heuristics. But even when it doesn’t do what I want, I’ve so far been okay with the results. The advantages vastly outweigh that.

Remaining problems

I need to write a test suite for the fundamental style (and maybe the others). This isn’t hard, it’s just a bit laborious so I haven’t gotten round to it yet.

There’re some parts of the AST I haven’t finished filling out. You can see them which are marked by FIXME’s. This just means if you try to format a node type it doesn’t know how to print, you’ll get a message saying so. Your code won’t be touched.

Comment re-insertion is a little bit of a challenge. I have a decent implementation that generally preserves comments well. There’re some corner cases that I’ve noticed, but I’m confident I have the right change to make to clear that up.

The fundamental printer is fast. My personal ChrisDone style is slower, due to its heuristics of deciding when to layout a certain way. It took 6s to layout a complex and large declaration. I updated my style and brought it down to 2s. That’s okay for now. There are always speed tricks that can be done.

There are of course issues like whether HSE can parse your code, whether you have #ifdef CPP pragmas in your code, and things like that. That’s just part of the general problem space of tools like this.

Remaining ideas

Currently you can only reformat a declaration. I don’t yet trust (any) Haskell printer with my whole file. I invoke it on a per-declaration basis and I see the result. That’s good for me at the moment. But in the future I might extend it to support whole modules.

Implement some operator-specific layouts. There are some operators that can really only be laid out in a certain way. Control.Applicative operators spring to mind:

Foo <$> foo <*> bar <*> mu

This can easily be handled as part of a style. Other considerations might be strings of lens operators. I’ve noticed that people tend not to put spaces around them, like:4


There’s also alignment, which is another possibility and easily implemented. The challenge will be deciding when alignment will look good versus making the code too wide and whitespacey. In my own style I personally haven’t implemented any alignment as it’s not that important to me, but I might one day.


Hopefully I’ve motivated the case that style is important, that formalizing style is important, and that automating it is practical and something we should solve and then move on, redirect our energy that was wasted on manually laying things out and debating.

  1. Granted, this isn’t a technical consideration. But it’s a real one.

  2. Both of these are referring to conventions other than simple layout, but I don’t think that detracts the point.


  4. I don’t know lens’s operators so that might not be real code, but the point is that could be a style to implement.

Categories: Offsite Blogs

Christopher Done: Formatting in Haskell


This post is about the formatting package.

What’s wrong with printf?

The Text.Printf module is problematic simply because it’s not type-safe:

λ> import Text.Printf λ> printf "" 2 *** Exception: printf: formatting string ended prematurely λ> printf "%s" 2 *** Exception: printf: bad formatting char 's'

And it’s not extensible in the argument type. The PrintfType class does not export its methods.

And it’s not extensible in the formatting. You can’t add a “%K” syntax to it to print a value in Kelvins, for example.

And it’s implicit. You can’t just use your normal API searching facilities to search how to print a Day.

Holy Moly!

A while ago I was inspired by the HoleyMonoid package to use that mechanism to make a general replacement for printf.

It’s a continuation-based way of building up monoidal functions by composition with the ability to insert constants in-between. Example:

let holey = now "x = " . later show . now ", y = " . later show > run holey 3 5 "x = 3, y = 5"

The now function inserts a monoidal value directly into the composition. So

run (now x . now y)

is equivalent to

x <> y


run (later show . now x . later show . now y)

is equivalent to

\a b -> show a <> x <> show b <> y The Formatting package

The package is available on Hackage as formatting.

Comparison with other formatters


format ("Person's name is " % text % ", age is " % hex) "Dave" 54

or with short-names:

format ("Person's name is " % t % ", age is " % x) "Dave" 54

Similar to C’s printf:

printf("Person's name is %s, age is %x","Dave",54);

and Common Lisp’s FORMAT:

(format nil "Person's name is ~a, age is ~x" "Dave" 54) The Holey type newtype HoleyT r a m = Holey { runHM :: (m -> r) -> a } type Holey m r a = HoleyT r a m

This is my version of the HoleyMonoid. To make this into a useful package I changed a few things.

The Category instance implied a name conflict burden with (.), so I changed that to (%):

(%) :: Monoid n => Holey n b c -> Holey n b1 b -> Holey n b1 c

Rather than have the name-conflicting map function, I flipped the type arguments of the type and made it an instance of Functor.


There is an array of top-level printing functions for various output types:

-- | Run the formatter and return a lazy 'Text' value. format :: Holey Builder Text a -> a -- | Run the formatter and return a strict 'S.Text' value. sformat :: Holey Builder S.Text a -> a -- | Run the formatter and return a 'Builder' value. bprint :: Holey Builder Builder a -> a -- | Run the formatter and print out the text to stdout. fprint :: Holey Builder (IO ()) a -> a -- | Run the formatter and put the output onto the given 'Handle'. hprint :: Handle -> Holey Builder (IO ()) a -> a

All the combinators work on a lazy text Builder which has good appending complexity and can output to a handle in chunks.

The Format type

There is a short-hand type for any formatter:

type Format a = forall r. Holey Builder r (a -> r)

All formatters are written in terms of now or later.


There is a standard set of formatters in Formatting.Formatters, for example:

text :: Format Text int :: Integral a => Format a sci :: Format Scientific hex :: Integral a => Format a

Finally, there is a general build function that will build anything that is an instance of the Build class from the text-format package:

build :: Buildable a => Format a

For which there are a bunch of instances. See the README for a full set of examples.

Composing formatters

%. is like % but feeds one formatter into another:

λ> format (left 2 '0' %. hex) 10 "0a" Extension

You can include things verbatim in the formatter:

> format (now "This is printed now.") "This is printed now."

Although with OverloadedStrings you can just use string literals:

> format "This is printed now." "This is printed now."

You can handle things later which makes the formatter accept arguments:

> format (later (const "This is printed later.")) () "This is printed later."

The type of the function passed to later should return an instance of Monoid.

later :: (a -> m) -> Holey m r (a -> r)

The function you format with (format, bprint, etc.) will determine the monoid of choice. In the case of this library, the top-level formating functions expect you to build a text Builder:

format :: Holey Builder Text a -> a

Because builders are efficient generators.

So in this case we will be expected to produce Builders from arguments:

format . later :: (a -> Builder) -> a -> Text

To do that for common types you can just re-use the formatting library and use bprint:

> :t bprint bprint :: Holey Builder Builder a -> a > :t bprint int 23 bprint int 23 :: Builder

Coming back to later, we can now use it to build our own printer combinators:

> let mint = later (maybe "" (bprint int)) > :t mint mint :: Holey Builder r (Maybe Integer -> r)

Now mint is a formatter to show Maybe Integer:

> format mint (readMaybe "23") "23" > format mint (readMaybe "foo") ""

Although a better, more general combinator might be:

> let mfmt x f = later (maybe x (bprint f))

Now you can use it to maybe format things:

> format (mfmt "Nope!" int) (readMaybe "foo") "Nope!" Retrospective

I’ve been using formatting in a bunch of projects since writing it. Happily, its API has been stable since releasing with some additions.

It has the same advantages as Parsec. It’s a combinator-based mini-language with all the same benefits.

Categories: Offsite Blogs

Craig Gentry of IBM

haskell-cafe - Fri, 09/19/2014 - 5:48pm
Hi, Gentry is doing on homomorphic functions cryptography. I looked on Hackage but did see a homomorphic function library. Is there.any effort in this area in Haskell? If so by whom and is contact info? Vasya _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >
Categories: Offsite Discussion

What about implicit data for typeclasses?

Haskell on Reddit - Fri, 09/19/2014 - 3:54pm

So this is just an idea I've been spitballing while I'm supposed to be working, but I remember a discussion recently about the negative sides of typeclasses and instead encouraging the use of data types that contain the implementation for the class and the specific data type. This approach seemed interesting as it allowed explicit control of the type class implementation, but had the side effect of making the code more verbose.

What I've been thinking about, is what if we could create implicit definitions (like in Scala) that can get plugged in to implicit function parameters when in scope. The benefit of this is

  1. The ability to explicitly provide implementations of if needed
  2. The ability to override implementations by choosing that which is closest in scope (not as relevant in Haskell because we don't tend to create as many block scopes as in Scala, but could be useful)
  3. Have typeclasses and their implementations be values in Haskell ready to work with.
submitted by kcuf
[link] [22 comments]
Categories: Incoming News

Sum and Product do not respect the Monoid laws

haskell-cafe - Fri, 09/19/2014 - 2:58pm
The Monoid instances for Sum and Product do not respect the Monoid laws. The instances are: Num a => instance Monoid (Sum a) Num a => instance Monoid (Product a) Float and Double are instances of the Num typeclass, however, floating point addition and multiplication are not associative. Here's an example: Sum {getSum = 1280.2457399999998} Sum {getSum = 1280.24574} Shouldn't these instances be constrained to Integral types? Jason _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >
Categories: Offsite Discussion

move sandboxes

haskell-cafe - Fri, 09/19/2014 - 11:13am
Hi guys, is there a pratical way to move a sandbox? I see the absolute path are hard-coded in all the .conf files. I ask the question because I have an application that uses Hint. So it needs to run with the same object files that it was compiled with. If I want to deploy the application on a server, I need to send the whole sandbox there: this way Hint/GHC finds the database when I start with "cabal exec". But this forces me to deploy it on the same path it was compiled, which is not very practical. Cheers C _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >
Categories: Offsite Discussion

preventing space leaks?

haskell-cafe - Fri, 09/19/2014 - 9:00am
Hi Cafe, I'm very new to Haskell, and I'm confused about haskell space leaks, even I read some wiki pages from Below is the scenario I''m facing at: When I use listArray to create either IArray or UArray, I found it could lead to space leaks (very high GC time), is there a way to prevent this, and why there is no fusion when create IArray/UArray from the list? I don't need the list anyway after array is created. (I used this few times for DP, based on this link: Further more, suppose if I create a IArray A from list 1, later I create UArray B based some computations based on A (also I need discard another list 2). After B is generated, I don't need A anymore (so this lead to space leaks, correct)? Another quetion, by the way, after the lazy IArray is created (say from a DP), is there a way convert it to UArray for better performance (IArray -> UArray)? How can I improve the space leak problems with above use case? Best Regards Baojun ________
Categories: Offsite Discussion

Performance impact of own Prelude

Haskell on Reddit - Fri, 09/19/2014 - 8:14am

The existing Prelude has a lot of great stuff but it also has some decisions that one might not agree with but can't easily be changed because the changes would be breaking, etc.

My question is, what if one creates an own Prelude that follows better practices (e.g. defining Monad, etc. like so and getting rid of all the duplicate functions) would there be any performance impact? Must of Prelude could be re-exported but a lot of the major classes would have to be rewritten and all the code that uses them rewritten. Is e.g. GHC doing anything special for the known Prelude or is it all things I could use as well (e.g. INLINE, etc.)?

EDIT: Also, what other downsides would there be besides the obvious incompatibility (i.e. users of normal Prelude couldn't just copy/paste code written with a custom Prelude)?

submitted by haskell101
[link] [15 comments]
Categories: Incoming News

JP Moresmau: A new Haskell IDE!

Planet Haskell - Fri, 09/19/2014 - 7:15am
Well, that title is click-bait. It's only a proof of concept, so far (-:, sorry!

I wanted to play with Threepenny-GUI since it allowed to do UI the FRP way, without having the troubles of getting a proper UI library to work. And I was going through a period of frustration with EclipseFP, so I thought about something else for a while... It's got the romantic name of HWIDE!

So in fact, this is a very simple integration of CodeMirror and Threepenny-GUI, to be able to edit Haskell sources inside your browser. When you save your buffer, the data is written to disk, and if a cabal file could be found for that source file, a cabal build (in a sandbox) is attempted (with a configure if needed). The output is then parsed by code ripped off BuildWrapper, and the errors/warnings are displayed, so you can click on them and see the offending line in the code.

That's all, really, and even that is not 100% perfect, but it's a start. I could get to play a bit with Events and Behaviors, develop some little widgets. If some FRP experts want to have a look at the code and offer some advice, I'd be all ears!

I probably won't have much time to turn this into the next generation Haskell IDE, but please fork and hack to your heart's content! The repository is at

Happy Haskell Hacking!
Categories: Offsite Blogs

Haskell FFI Question

haskell-cafe - Fri, 09/19/2014 - 5:32am
I have been play around with Haskell FFI. My question is for ByteString (Strict) is there a trailing null append to it when pass to it C functions? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >
Categories: Offsite Discussion

What is wrong with the Monoid instance for Maybe?

Haskell on Reddit - Fri, 09/19/2014 - 5:16am

Looking through the documentation for semigroups I found this entry:

Option is effectively Maybe with a better instance of Monoid, built off of an underlying Semigroup instead of an underlying Monoid.

Ideally, this type would not exist at all and we would just fix the Monoid instance of Maybe

Does anyone know what is wrong with the Maybe Monoid instance?

submitted by haskell101
[link] [21 comments]
Categories: Incoming News

ICFP 2014 : Program - Thu, 09/18/2014 - 11:48pm
Categories: Offsite Blogs

Proposal: Add a few extra members to Foldable and Traversable classes

libraries list - Thu, 09/18/2014 - 10:37pm
To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose: Add `null` and `size` to the Foldable class. Default implementations: null = foldr (\_ _ -> False) True size = foldl' (\acc _ -> acc+1) 0 Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple. David _______________________________________________ Libraries mailing list Libraries< at >
Categories: Offsite Discussion

Reimplementing Streams, Lists, and Tries with Fix, Free, Product and Compose

Haskell on Reddit - Thu, 09/18/2014 - 7:34pm

So I've been playing around with some wrapper types I'm sure I've only rediscovered, using them to reimplement some standard types:

newtype Product1 f g a = Product1 { getProduct1 :: (f a, g a) } instance (Functor f, Functor g) => Functor (Product1 f g) where fmap f = Product1 . (fmap f *** fmap f) . getProduct1 newtype Sum1 f g a = Sum1 { getSum1 :: Either (f a) (g a) } instance (Functor f, Functor g) => Functor (Sum1 f g) where fmap f = Sum1 . (fmap f +++ fmap f) . getSum1 newtype Fix1 f a = Fix1 { getFix1 :: f (Fix1 f) a } instance Functor (f (Fix1 f)) => Functor (Fix1 f) where fmap f = Fix1 . fmap f . getFix1 newtype Compose1 f g a b = Compose1 { getCompose1 :: f (g a) b } instance (Functor (f (g a))) => Functor (Compose1 f g a) where fmap f = Compose1 . fmap f . getCompose1 newtype Double1 f g a = Double1 { getDouble1 :: f g g a } instance Functor (f g g) => Functor (Double1 f g) where fmap f = Double1 . fmap f . getDouble1 type Free1 f = Fix1 (Sum1 Identity `Compose1` f) -- Free1 f a ~ Either a (f (Free1 f) a) type Link = Product1 Identity -- Link a ~ (a, f a) type Stream = Fix1 Link -- Stream a ~ (a, Stream a) type List = Fix1 (Compose Maybe `Compose1` Link) -- List a ~ Maybe (a, List a) type NonEmptyList = Fix1 (Link `Compose1` Compose Maybe) -- NonEmptyList a ~ (a, Maybe (NonEmptyList a)) type Trie f = Fix1 (Product1 Maybe `Compose1` Compose f) -- Trie f a ~ (Maybe a, f (Trie f a)) type TrieForest f = Fix1 (Compose f `Compose1` Product1 Maybe) -- TrieForest f a ~ f (Maybe a, TrieForest f a) type BinaryTree = Free1 (Double1 Product1) -- BinaryTree a ~ Either a (BinaryTree a, BinaryTree a) type BST i = Free1 (Product1 (Const i) `Compose1` Double1 Product1) -- BST i a ~ Either a (BST i a, i, BST i a)

Are there more standard names for these types? Is there a collective name for this kind of variant, or somewhere I can go to read up more on them?

submitted by rampion
[link] [4 comments]
Categories: Incoming News