# News aggregator

### Mark Jason Dominus: A message to the aliens, part 10/23 (temperature)

Earlier articles: Introduction Common features Page 1 (numerals) Page 2 (arithmetic) Page 3 (exponents) Page 4 (algebra) Page 5 (geometry) Page 6 (chemistry) Page 7 (mass) Page 8 (time and space) Page 9 (physical units)

This is page 10 of the *Cosmic Call*
message. An explanation follows.

The 10 digits are:

0

1

2

3

4

5

6

7

8

9

The top half of this page is a table of melting points (on the left) and boiling points (on the right) for various substances: hydrogen , carbon , sulfur , zinc , silver , and gold . The temperatures are given in kelvins .

The boiling points depend on pressure, so there is a notation at the bottom of the list that the pressure should be 101300 pascals . This is one standard atmosphere, so it may tell the aliens a little more about our planet.

To help calibrate the kelvins, the bottom of the page is a chart of the temperature increase of water , showing how the temperature stops increasing at the melting point (273K) and the boiling point (373K). This introduces the glyph for temperature , which will recur later.

There are two regrettable things about this chart. One is that the horizontal axis is labeled “time” . Why is the temperature of the water increasing with time? It should be energy.

But a more serious complaint, I think, it that this is the wrong
chart. It depends crucially on the (Earth-)standard atmospheric pressure,
with which the recipients may not be familiar. And the kelvin is not defined
in terms of standard pressure anyway. It is defined in terms of the
triple point of water, the unique, universal temperature and pressure at which
all three states of water can coexist. Why not a temperature and
pressure chart with the triple point labeled? This is something one
might more reasonably expect the aliens to have studied.

### ANN ghc-mod-5.4.0.0, now with Stack support!

### Sound advice

### Converting EpochTime to Integer

### Good Mid-Sized Projects For Learning Haskell

I've gone through: https://github.com/bitemyapp/learnhaskell, have read bits and pieces of RWH and LYAH, Typeclassopedia, and the like.

I want to solidify my haskell knowledge by embarking on a medium sized project. I'm the type who likes spending his time building concrete, useful things. As such, I'd like to work on something that either I or someone else would use.

Could you guys help me come up with ideas for projects?

submitted by RunningIntoTunnels[link] [20 comments]

### The MonadState, ... class

Why aren't there MonadState, MonadExcept, ... classes in the transformers package? It seems that get, set, throwE could be implemented in custom monads and get, set, ... could easily be delegated from compound monad to its appropriate component. Am I just naive and expect something that no one would appreciate or is it simply not useful/possible for other reasons that I don't see. Personally I would really like it sorted between transformers and mtl. It is so confusing to newcomers (like me) to have to deal with 2 libraries that partially overlap. Why can't there be one full featured library and then another for backward compatibility while it makes sense to "maintain" it.

submitted by jd823592[link] [19 comments]

### π-Base, a community database of topological examples with automated deduction [xpost /r/math]

### Great UI on Haskell site and subreddit. Anyone know designed it?

I know it's not new or anything, but every time I go to the front page I get a feeling that the design is close to perfect. I visit a lot of sites and rarely get that impression. Who's behind it, and are they for hire?

submitted by AaronArtille[link] [comment]

### My first proper Haskell program. I think I need to read a monad tutorial or something.

I read LYAH once upon a time, but the bits toward the end are a bit fuzzy. I had planned to read the chapters on monads and then try this, but after the internet went out today morning I decided to just do it and see what I ended up reinventing. (Have I, actually?)

So: this is an implementation of a fixed-size stack (I learned how to use Data.Vector in the process) that I was originally given as a homework problem in school (in Java, not Haskell!), with a pointer that points to the "top" element. Elements beyond the top are disregarded and may be overwritten.

My pop function has a signature of Stack a -> Maybe a, as I think it should, but I ended up having a lot of trouble unwrapping the Maybes everywhere.

I then implemented a reverse Polish notation evaluator with the stack datatype. Easy enough, but . . . I actually had to access the underlying vector at one point (instead of doing everything with the push, pop and peek functions; it became too complicated otherwise)! How do I not do that?

I'm sure there is a lot of stupid in the code. At the very least, it's probably extremely unidiomatic in places. Please tell me how I can fix all of that.

Lastly, it was a great experience writing a large (for me) program without any looping or mutation. It's definitely taught me to think somewhat differently -- more so because I couldn't rely on Stack Overflow or #haskell or anything. :)

submitted by octatoan[link] [27 comments]

### Replicating GADTs with existential types in Java... Crudely, of course.

I've embarked on something awful. I'm trying to write in a purely functional style using Java, just because I need to do a project in Java. The first thing I did was think up how I was going to replicated ADTs. Turns out pretty easy.

public interface ADTName<A> { <R> R match(Function<Constructor1<A>, R> f, Function<Constructor2<A>, R> f2); // Useful default methods represent functions on an instance of ADTName ... } public final class Constructor1<A> implements ADTName<A> { @Override public <R> R match(Function<Constructor1<A>, R> f, Function<Constructor2<A>, R> f2) { return f.apply(this); } } public final class Constructor2<A> implements ADTName<A> { @Override public <R> R match(Function<Constructor1<A>, R> f, Function<Constructor2<A>, R> f2) { return f2.apply(this); } }Simple enough. The constructors can have whatever constructors and instance variables you need. It's clumsy and verbose, but it works. Now we can write stuff like this:

Boolean b = instance.match( c1 -> true, c2 -> false );Of course those expressions can be dependent on the actual matches, making use of methods and variables in the constructor classes in a type safe manner.

Next, I needed a way to use an existential GADT. Well GADTs are easy enough.

public interface GADTName<A, B> { <R> R match(Function<C1, R> f, Function<C2<A>, R> f2); } public final class C1 implements GADTName<Integer, Boolean> { @Override public <R> R match(Function<C1, R> f, Function<C2<A>, R> f2) { return f.apply(this); } } public final class C2<A> implements GADTName<A, String> { @Override public <R> R match(Function<C1, R> f, Function<C2<A>, R> f2) { return f2.apply(this); } }Honestly, the simplicity in advancing to GADTs surprised me. With some generic constraints this can do most everything a universal GADT can do.

But an existential GADT has proven problematic. It's start out easy enough. You just add a type parameter to the constructor subclasses, and those types behave as existentials. The problem is actually using them. Take this Haskell example.

data ExGADTName a where C1 :: a -> (a -> b) -> ExGADTName bThe Java equivalent data structure is like this.

public interface ExGADTName<A> { <R> R match(Function<C1<?, A>, R> f); } public final class C1<A, B> implements GADTName<B> { public final A a; public final Function<A, B> f; public C1(A a, Function<A, B> f) { this.a = a; this.f = f; } @Override public <R> R match(Function<C1<?, B>, R> matcher) { return matcher.apply(this); } }Of course, in this case, you can just make a method in the C1 class that calls f for you using the a parameter. And of course this whole example can be replaced by only using the C1 class, ignoring the desire for the overarching GADT interface. But that's not the point. The point is, in Java, there's no way to take that wildcard (?) in the match and make use of it.

ExGADTName<B> instance = new C1<A, B>(...); B b = instance.match( c1 -> c1.f.apply(c1.a) // errors );The A type is essentially lost in translation, and rightfully so. But in the match, there needs to be a way to get it back. In haskell, it Just Works™, because of its support for existential types. But in Java, it just sees that apply() takes a wild card, c1.a is a wildcard, and doesn't see any reason that those wildcards should match.

This answer on stackoverflow provides a method that would work fine for this particular situation, but it's not always applicable. Consider something like this with its accompanying Applicative instance.

data Type a where C1 :: a -> Type (a -> b) -> Type b C2 :: a -> Type a instance Functor Type where fmap f (C1 x p) = C1 x $ fmap (f .) p fmap f (C2 x) = C2 $ f x instance Applicative Type where pure = C2 C1 x p <*> q = C1 x $ flip <$> p <*> q C2 f <*> q = fmap f qIt's interesting to implement. The data structure is easy enough.

public interface Type<A> { <R> R match(Function<C1<?, A>, R> f, Function<C2<A>, R> f2); } public final class C1<A, B> implements Type<B> { public final A x; public final Type<Function<A, B>> p; public C1(...) {...} @Override public <R> R match(Function<C1<?, B>, R> f, Function<C2<B>, R> f2) { return f.apply(this); } } public final class C2<A> implements Type<A> { public final A x; public C2(...) {...} @Override public <R> R match(Function<C1<?, A>, R> f, Function<C2<A>, R> f2) { return f2.apply(this); } }But the instances get a little strange. The fmap function can't be done statically, for the same reasons as the sequencing operator that I'll get to in a minute. But it can be done virtually, by requiring overrides.

public interface Type<A> { ... <B> Type<B> fmap(Function<A, B> f); } public final class C1<A, B> implements Type<B> { ... @Override public <C> Type<C> fmap(Function<B, C> f) { return new C1<A, C>(x, p.fmap(f::compose)); } } public final class C2<A> implements Type<A> { ... @Override public <B> Type<B> fmap(Function<A, B> f) { return new C2<B>(f.apply(x)); } }Applicative is where it gets interesting. We can't keep using the inheritance hack like we did for Functor. Instance methods in java aren't allowed to restrict type parameters. So the operator has to be implemented as a static method.

public interface Type<A> { ... static <A> Type<A> pure(A x) { return new C2<>(x); } static <A, B> Type<B> seq(Type<Function<A, B>> f, Type<A> q) { return f.match( c1 -> (...), // ??? c2 -> q.fmap(c2.x) ); } }Problem is, as a static method, c1's wildcard can't be used as a type at all. Even if you made a generic method that had all the type parameters, you can't pass c1 into it because wildcards don't match arbitrary generics. So I can't write this code in Java.

C1 x p <*> q = C1 x $ flip <$> p <*> qSolving this problem would require an instance method that's aware that the type parameter is a function. But this isn't possible.

Have I reached the limit of Java's type system? Or is there a way to work with this and get it working?

submitted by ElvishJerricco[link] [19 comments]

### Haskell related search engines in the Opera browser

### Powerset of a set

### Neil Mitchell: Making sequence/mapM for IO take O(1) stack

*Summary: We have a version of mapM for IO that takes O(1) stack and is faster than the standard Haskell/GHC one for long lists.*

The standard Haskell/GHC base library sequence function in IO takes *O(n)* stack space. However, working with Tom Ellis, we came up with a version that takes *O(1)* stack space. Our version is slower at reasonable sizes, but faster at huge sizes (100,000+ elements). The standard definition of sequence (when specialised for both IO and []) is equivalent to:

sequence [] = return []

sequence (x:xs) = do y <- x; ys <- sequence xs; return (y:ys)

Or, when rewritten inlining the monadic bind and opening up the internals of GHC's IO type, becomes:

sequence :: [IO a] -> IO [a]sequence [] = IO $ \r -> (# r, () #)

sequence (y:ys) = IO $ \r -> case unIO y r of

(# r, y #) -> case unIO (sequence xs) r of

(# r, ys #) -> (# r, y:ys #)

For those not familiar with IO, it is internally defined as:

newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #)Each IO action takes a RealWorld token and returns a RealWorld token, which ensures that IO actions run in order. See here for a full tutorial.

Our observation was that this version requires *O(n)* stack space, as each recursive call is performed inside a case. The algorithm proceeds in two phases:

- First, it traverses the input list, evaluating each action and pushing y on the stack.
- After reaching the [] at the end of the list, it traverses the stack constructing the output list.

By constructing the list directly on the heap we can avoid the extra copy and use *O(1)* stack. Our version is:

sequenceIO xs = do

ys <- IO $ \r -> (# r, apply r xs #)

evaluate $ demand ys

return ys

where

apply r [] = []

apply r (IO x:xs) = case x r of

(# r, y #) -> y : apply r xs

demand [] = ()

demand (x:xs) = demand xs

Here the two traversals are explicit:

- First, we traverse the list using apply. Note that we pass the RealWorld token down the list (ensuring the items happen in the right order), but we do not pass it back.
- To ensure all the IO actions performed during apply happen before we return any of the list, we then demand the list, ensuring the [] element has been forced.

Both these traversals use *O(1)* stack. The first runs the actions and constructs the list. The second ensures evaluation has happened before we continue. The trick in this algorithm is:

Here we cheat by duplicating r, which is potentially unsafe. This line does not evaluate apply, merely returns a thunk which when evaluated will force apply, and cause the IO to happen during evaluation, at somewhat unspecified times. To regain well-defined evaluation order we force the result of apply on the next line using demand.

**Benchmarks**

We benchmarked using GHC 7.10.2, comparing the default sequence (which has identical performance to the specialised monomorphic variant at the top of this post), and our sequenceIO. We benchmarked at different lengths of lists. Our sequenceIO is twice as slow at short lists, draws even around 10,000-100,000 elements, and goes 40% faster by 1,000,000 elements.

Our algorithm saves allocating stack, at the cost of iterating through the list twice. It is likely that by tuning the stack allocation flags the standard algorithm would be faster everywhere.

**Using sequence at large sizes**

Despite improved performance at large size, we would not encourage people to use sequence or mapM at such large sizes - these functions still require *O(n)* memory. Instead:

- If you are iterating over the elements, consider fusing this stage with subsequence stages, so that each element is processed one-by-one. The conduit and pipes libraries both help with that approach.
- If you are reducing the elements, e.g. performing a sum, consider fusing the mapM and sum using something like foldM.

For common operations, such a concat after a mapM, an obvious definition of concatMapM is:

concatMapM :: Monad m => (a -> m [b]) -> [a] -> m [b]concatMapM f = liftM concat . mapM f

But that if the result of the argument is regularly [] then a more efficient version is:

concatMapM op = foldr f (return [])where f x xs = do x <- op x

if null x then xs else liftM (x ++) xs

For lists of 10,000 elements long, using the function const (return []), this definition is about 4x faster. Version 1.4.2 of the extra library uses this approach for both concatMapM and mapMaybeM.