# News aggregator

### No `base-4.7.0.1` in hackage

### Cabal question

### Dominic Steinitz: Fun with (Kalman) Filters Part I

Suppose we wish to estimate the mean of a sample drawn from a normal distribution. In the Bayesian approach, we know the prior distribution for the mean (it could be a non-informative prior) and then we update this with our observations to create the posterior, the latter giving us improved information about the distribution of the mean. In symbols

Typically, the samples are chosen to be independent, and all of the data is used to perform the update but, given independence, there is no particular reason to do that, updates can performed one at a time and the result is the same; nor is the order of update important. Being a bit imprecise, we have

The standard notation in Bayesian statistics is to denote the parameters of interest as and the observations as . For reasons that will become apparent in later blog posts, let us change notation and label the parameters as and the observations as .

Let us take a very simple example of a prior where is known and then sample from a normal distribution with mean and variance for the -th sample where is known (normally we would not know the variance but adding this generality would only clutter the exposition unnecessarily).

The likelihood is then

As we have already noted, instead of using this with the prior to calculate the posterior, we can update the prior with each observation separately. Suppose that we have obtained the posterior given samples (we do not know this is normally distributed yet but we soon will):

Then we have

Writing

and then completing the square we also obtain

More Formally

Now let’s be a bit more formal about conditional probability and use the notation of -algebras to define and where , is as before and . We have previously calculated that and that and the tower law for conditional probabilities then allows us to conclude . By Jensen’s inequality, we have

Hence is bounded in and therefore converges in and almost surely to . The noteworthy point is that if if and only if converges to 0. Explicitly we have

which explains why we took the observations to have varying and known variances. You can read more in Williams’ book (Williams 1991).

A Quick CheckWe have reformulated our estimation problem as a very simple version of the celebrated Kalman filter. Of course, there are much more interesting applications of this but for now let us try “tracking” the sample from the random variable.

> {-# OPTIONS_GHC -Wall #-} > {-# OPTIONS_GHC -fno-warn-name-shadowing #-} > {-# OPTIONS_GHC -fno-warn-type-defaults #-} > {-# OPTIONS_GHC -fno-warn-unused-do-bind #-} > {-# OPTIONS_GHC -fno-warn-missing-methods #-} > {-# OPTIONS_GHC -fno-warn-orphans #-} > module FunWithKalmanPart1 ( > obs > , nObs > , estimates > , uppers > , lowers > ) where > > import Data.Random.Source.PureMT > import Data.Random > import Control.Monad.State > var, cSquared :: Double > var = 1.0 > cSquared = 1.0 > > nObs :: Int > nObs = 100 > createObs :: RVar (Double, [Double]) > createObs = do > x <- rvar (Normal 0.0 var) > ys <- replicateM nObs $ rvar (Normal x cSquared) > return (x, ys) > > obs :: (Double, [Double]) > obs = evalState (sample createObs) (pureMT 2) > > updateEstimate :: (Double, Double) -> (Double, Double) -> (Double, Double) > updateEstimate (xHatPrev, varPrev) (y, cSquared) = (xHatNew, varNew) > where > varNew = recip (recip varPrev + recip cSquared) > xHatNew = varNew * (y / cSquared + xHatPrev / varPrev) > > estimates :: [(Double, Double)] > estimates = scanl updateEstimate (y, cSquared) (zip ys (repeat cSquared)) > where > y = head $ snd obs > ys = tail $ snd obs > > uppers :: [Double] > uppers = map (\(x, y) -> x + 3 * (sqrt y)) estimates > > lowers :: [Double] > lowers = map (\(x, y) -> x - 3 * (sqrt y)) estimates BibliographyWilliams, David. 1991. *Probability with Martingales*. Cambridge University Press.

### Speeding up Data.List.inits

### Connection between Monad, Functor and Applicative

Hi,

as far as I understand Monad, Functor and Applicative definitely have something in common. For example, is there any instance of Applicative that isn't basically:

instance Applicative Foo where pure = return (<*>) = apAlso, is every Monad a Functor and Applicative or are there examples for types that are only one of the three classes?

submitted by Dibib[link] [18 comments]

### Please Critique my First Project - A Bitcoin Market API Client

Hiya, so I've spent the last 2 months or so learning Haskell. I've finished the UPenn course, LYAH and a little bit of RWH.

I wanted to get a project going so I tried making an API client for the CampBX Bitcoin Market[1]. I started out by following along with the FPComplete Mailchimp API Tutorial[2].

I'm asking you beautiful people for any feedback on it so I can be sure that I'm on the right track here, stuff like code style/idioms, project layout, public interface, implementation, docs, ideas for new features, anything you want to tell me, etc.:

https://github.com/prikhi/campbx-haskell

Typical usage would be something like this[3]:

main :: IO () main = do cfg <- defaultCampBXConfig _ <- runCampBX cfg $ do totalAskVolume <- calculateAskVolume <$> getDepth liftIO . putStrLn $ "Total Ask Volume: " ++ show totalAskVolume return () calculateAskVolume :: Depth -> BTCAmount calculateAskVolume depthList = sum . map askAmount . asks $ depthList where askAmount (Ask (_, q)) = qThere are still some things I want to work on:

- Define Asks and Bids[4] using Record Syntax. The JSON[5] for a Bid/Ask comes back as a 2 item Array but the generically derived instance[6] expects an object. I haven't completely wrapped my head around Aeson's Array parsing...
- Write tests. I'm imagining they would be more "given this JSON, make sure the data structure is created correctly" instead of property-based testing.
- Use something other than Doubles to represent Amounts + Prices. Is there a standard library for accurate math with decimals(I need up to 8 decimal places)? I suppose I could always just use Integers to represent Satoshis(the smallest subunit of bitcoins).

Also I tried adding "default-extensions: OverloadedStrings" to the .cabal file and removing the pragmas from the source files, but the package wouldn't build :(

[1] https://campbx.com/api.php

[3] https://github.com/prikhi/campbx-haskell/blob/master/bin/CampBXMain.hs

[4] https://github.com/prikhi/campbx-haskell/blob/master/src/Web/CampBX/Types.hs#L71

[5] http://sleepanarchy.com/p/K1wuSm

[6] https://github.com/prikhi/campbx-haskell/blob/master/src/Web/CampBX/Types.hs#L188

submitted by ComradeRikhi[link] [7 comments]

### When did you learn haskell?

I have been programming for 4-5 years, and i have been evolving my skills constantly, i have a CompSci degree, but i still feel like i am self-taught.

I have done a wide variety of stuff, but almost always OOP. Now i want to grasp the functional side, i really dont quite get what is all about yet.

I guess my questions are:

1) When did you learn functional programming, and was haskell your first func lang, if not, what was?

2) How has functional programming changed you way of programming?

3) Do you apply functional techiques successfully in non pure functional languages? (Eg. JavaScript)

submitted by gkunno[link] [19 comments]

### How should I learn Haskell?

I've been studying Python for a while, I finished up Learn Python the Hard Way, and I'm feeling really comfortable in that language. I decided next I'd learn Haskell, because I want to learn a functional language, and I hear it's a great way to get introduced into functional programming. So my question is, where do I go/what do I do to learn Haskell? I generally prefer physical books when I study things, it just works better for me, but if that's not the best way to learn Haskell, let me know!

EDIT: Thanks for your help everyone! Looks like I'll be buying LYAH!

submitted by PM_ME_WHATEVER_IM_BI[link] [21 comments]

### Avoiding BlockedIndefinitelyOnSTM exceptions

### Proposal: add 'equating' function to Data.List

### Keeping data synched between client/server?

Hey again. So, on my way to learning Haskell I've met another tricky problem. How do you keep data synchronised between client/server? Usually (on C++ etc) the approach would be to manually write socket messages for everything you want to synchronise. Can we do better? I guess some fast diff/patch algorithm for algebraic datatypes would be very handy?

submitted by SrPeixinho[link] [6 comments]

### Danny Gratzer: A Tutorial on Church Representations

I’ve written a few times about church representations, but never aimed at someone who’d never heard of what a church representation is. In fact, it doesn’t really seem like too many people have!

In this post I’d like to fix that :)

What is a Church RepresentationSimply put, a church representation (CR) is a way of representing a piece of concrete data with a function. The CR can be used through an identical way to the concrete data, but it’s comprised entirely of functions.

They where originally described by Alanzo Church as a way of modeling all data in lambda calculus, where all we have is functions.

TuplesThe simplest CR I’ve found is that of a tuples.

Let’s first look at our basic tuple API

type Tuple a b = ... mkTuple :: a -> b -> Tuple a b fst :: Tuple a b -> a snd :: Tuple a b -> bNow this is trivially implemented with (,)

type Tuple a b = (a, b) mkTuple = (,) fst = Prelude.fst snd = Prelude.sndThe church representation preserves the interface, but changes all the underlying implementations.

type Tuple a b = forall c. (a -> b -> c) -> cThere’s our church pair, notice that it’s only comprised of ->. It also makes use of higher rank types. This means that a Tuple a b can be applied to function producing *any* c and it must return something of that type.

Let’s look at how the rest of our API is implemented

mkTuple a b = \f -> f a b fst tup = tup (\a _ -> a) snd tup = tup (\_ b -> b)And that’s it!

It’s helpful to step through some reductions here

fst (mkTuple 1 2) fst (\f -> f 1 2) (\f -> f 1 2) (\a _ -> a) (\a _ -> a) 1 2 1And for snd

snd (mkTuple True False) fst (\f -> f True False) (\f -> f True False) (\_ b -> b) (\_ b -> b) True false FalseSo we can see that these are clearly morally equivalent. The only real question here is whether, for each CR tuple there exists a normal tuple. This isn’t immediately apparent since the function type for the CR looks a lot more general. In fact, the key to this proof lies in the forall c part, this extra polymorphism let’s us use a powerful technique called “parametricity” to prove that they’re equivalent.

I won’t actually go into such a proof now since it’s not entirely relevant, but it’s worth noting that both (,) and Tuple are completely isomorphic.

To convert between them is pretty straightforward

isoL :: Tuple a b -> (a, b) isoL tup = tup (,) isoR :: (a, b) -> Tuple a b isoR (a, b) = \f -> f a bNow that we have an idea of how to church representations “work” let’s go through a few more examples to start to see a pattern.

BooleansBooleans have the simplest API of all

type Boolean = ... true :: Boolean false :: Boolean test :: Boolean -> a -> a -> aWe can build all other boolean operations on test

a && b = test a b false a || b = test a true b when t e = test t e (return ())This API is quite simple to implement with Bool,

type Boolean = Bool true = True false = False test b t e = if b then t else eBut how could we represent this with functions? The answer stems from test,

type Boolean = forall a. a -> a -> aClever readers will notice this is almost identical to test, a boolean get’s two arguments and returns one or the other.

true = \a _ -> a false = \_ b -> b test b t e = b t eWe can write an isomorphism between Bool and Boolean as well

isoL :: Bool -> Boolean isoL b = if b then true else false isoR :: Boolean -> Bool isoR b = test b True False ListsNow let’s talk about lists. One of the interesting things is lists are the first recursive data type we’ve dealt with so far.

Defining the API for lists isn’t entirely clear either. We want a small set of functions that can easily cover *any* conceivable operations for a list.

The simplest way to do this is to realize that we can do exactly 3 things with lists.

- Make an empty list
- Add a new element to the front of an existing list
- Pattern match on them

We can represent this with 3 functions

type List a = ... nil :: List a cons :: a -> List a -> List a match :: List a -> b -> (a -> List a -> b) -> bIf match looks confusing just remember that

f list = match list g hIs really the same as

f [] = g f (x : xs) = h x xsIn this way match is just the pure functional version of pattern matching. We can actually simplify the API by realizing that rather than this awkward match construct, we can use something cleaner.

foldr forms a much more pleasant API to work with since it’s really the most primitive form of “recursing” on a list.

match :: List a -> (a -> List a -> b) -> b -> b match list f b = fst $ foldr list worker (b, nil) where worker x (b, xs) = (f x xs, cons x xs)The especially nice thing about foldr is that it doesn’t mention List a in its two “destruction” functions, all the recursion is handled in the implementation.

We can implement CR lists trivially using foldr

type List a = forall b. (a -> b -> b) -> b -> b nil = \ _ nil -> nil cons x xs = \ cons nil -> x `cons` xs cons nil foldr list cons nil = list cons nilNotice that we handle the recursion in the list type by having a b as an argument? This is similar to how the accumulator to foldr gets the processed tail of the list. This is a common technique for handling recursion in our church representations.

Last but not least, the isomorphism arises from foldr (:) [],

isoL :: List a -> [a] isoL l = l (:) [] isoR :: [a] -> List a isoR l f z = foldr f z l EitherThe last case that we’ll look at is Either. Like Pair, Either has 3 different operations.

type Or a b = ... inl :: a -> Or a b inr :: b -> Or a b or :: Or a b -> (a -> c) -> (b -> c) -> cThis is pretty easy to implement with Either

type Or a b = Either a b inl = Left inr = Right or (Left a) f g = f a or (Right b) f g = g bOnce again, the trick to encoding this as a function falls right out of the API. In this case we use the type of or

type Or a b = forall c. (a -> c) -> (b -> c) -> c inl a = \f g -> f a inr b = \f g -> g a or x = xLast but not least, let’s quickly rattle off our isomorphism.

isoL :: Or a b -> Either a b isoL o = o Left Right isoR o :: Either a b -> Or a b isoR o = or o The PatternSo now we can talk about the underlying pattern in CRs. First remember that for any type T, we have a list of n distinct constructors T1 T2 T3…Tn. Each of the constructors has a m fields T11, T12, T13…

Now the church representation of such a type T is

forall c. (T11 -> T12 -> T13 -> .. -> c) -> (T21 -> T22 -> T23 -> .. -> c) ... -> (Tn1 -> Tn2 -> Tn3 -> .. -> c) -> cThis pattern doesn’t map quite as nicely to recursive types. Here we have to take the extra step of substituting all occurrences of T for c in our resulting church representation.

This is actually such a pleasant pattern to work with that I’ve written a library for automatically reifying a type between its church representation and concrete form.

Wrap UpHopefully you now understand *what* a church representation is. It’s worth noting that a lot of stuff Haskellers stumble upon daily are really church representations in disguise.

My favorite example is maybe, this function takes a success and failure continuation with a Maybe and produces a value. With a little bit of imagination, one can realize that this is really just a function mapping a Maybe to a church representation!

If you’re thinking that CRs are pretty cool! Now might be a time to take a look at one of my previous posts on deriving them automagically.

<script type="text/javascript"> /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */ var disqus_shortname = 'codeco'; // required: replace example with your forum shortname /* * * DON'T EDIT BELOW THIS LINE * * */ (function() { var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true; dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq); })(); </script> <noscript>Please enable JavaScript to view the comments powered by Disqus.</noscript> comments powered by Disqus### Functional Programing-Oriented Machine LearningStartup Seeks DevOps Guru

### Conduit & state

### What about anonymous/inline types?

It was enlightening the first time one notices any kind of expression can be converted to a single tree of inlined anonymous functions and expressions.

bar a b = a + b foo a b = bar a b + bar a b `foo` can be inlined as not to depend on `bar` foo = λa → λb → ((λc → λd → c + d) a b) + ((λc → λd → c + d) a b)Might be obvious, but I don't know how to apply the same principle to types.

data Bar a = B a a data Foo = Foo Bar Bar data Foo = forall a. Foo (B a a) (B a a) -- ?? Nonsense submitted by SrPeixinho[link] [5 comments]

### Ken T Takusagawa: [gggpgqye] Narrow type signatures which can be widened

Create a tool to find type signatures that are less polymorphic than would be inferred by type inference.

This is a solution in search of a problem.

### Unable to build vector on OSX (ghc 7.4, gcc 4.8)

### Mark Jason Dominus: On uninhabited types and inconsistent logics

Earlier this week I gave a talk about the Curry-Howard
isomorphism. Talks never go quite
the way you expect. The biggest sticking point was my assertion that
there is no function with the type *a* → *b*. I mentioned this as a
throwaway remark on slide 7, assuming that everyone would agree
instantly, and then we got totally hung up on it for about twenty
minutes.

Part of this was my surprise at discovering that most of the audience (members of the Philly Lambda functional programming group) was not familiar with the Haskell type system. I had assumed that most of the members of a functional programming interest group would be familiar with one of Haskell, ML, or Scala, all of which have the same basic type system. But this was not the case. (Many people are primarily interested in Scheme, for example.)

I think the main problem was that I did not make clear to the audience
what Haskell means when it says that a function has type *a* → *b*. At the
talk, and then later on
Reddit
people asked

what about a function that takes an integer and returns a string:
doesn't it have type *a* → *b*?

If you know one of the HM languages, you know that of course it doesn't; it has type Int → String, which is not the same at all. But I wasn't prepared for this confusion and it took me a while to formulate the answer. I think I underestimated the degree to which I have internalized the behavior of Hindley-Milner type systems after twenty years. Next time, I will be better prepared, and will say something like the following:

A function which takes an integer and returns a string does not have
the type *a* → *b*; it has the type Int → String. You must pass it an
integer, and you may only use its return value in a place that makes
sense for a string. If *f* has this type, then 3 +
f 4 is a compile-time type error because Haskell knows that *f*
returns a string, and strings do not work with +.

But if *f* had
the type *a* → *b*, then 3 + f 4 would be legal, because context requires that
*f* return a number, and the type *a* → *b* says that it *can* return a
number, because a number is an instance of the completely general type
*b*. The type *a* → *b*, in contrast to Int → String, means that *b*
and *a* are completely unconstrained.

Say function *f* had type *a* → *b*. Then you would be able to use the
expression f x in any context that was expecting any sort of return
value; you could write any or all of:

and they would all type check correctly, regardless of the type of
*x*. In the first line, *f x* would return a number; in the second
line *f* would return a list; in the third line it would return a
string, and in the fourth line it would return a boolean. And in each
case *f* could be able to do what was required regardless of the type
of *x*, so without even looking at *x*. But how could you possibly
write such a function *f*? You can't; it's impossible.

Contrast this with the identity function id, which has type *a* → *a*. This says that id always returns a value whose type is the same as
that if its argument. So you can write

as long as *x* has the right type for +, and you can write

as long as x has the
right type for head, and so on. But for *f* to have the type *a* → *b*, all those
would have to work regardless of the type of the argument to *f*. And
there is no way to write such an *f*.

Actually I wonder now if part of the problem is that we like to write
*a* → *b* when what we really mean is the type ∀a.∀b.*a* → *b*. Perhaps making
the quantifiers explicit would clear things up? I suppose it probably
wouldn't have, at least in this case.

The issue is a bit complicated by the fact that the function

loop :: a -> b loop x = loop x*does* have the type *a* → *b*, and, in a language with exceptions, throw
has that type also; or consider Haskell

Unfortunately, just as I thought I was getting across the explanation
of why there can be no function with type *a* → *b*, someone brought up
exceptions and I had to mutter and look at my shoes. (You can also take
the view that these functions have type *a* → ⊥, but the logical
principle ⊥ → *b* is unexceptionable.)

In fact, experienced practitioners will realize, the instant the type
*a* → *b* appears, that they have written a function that never returns.
Such an example was directly responsible for my own initial interest
in functional programming and type systems; I read a 1992 paper (“An
anecdote about ML type
inference”)
by Andrew R. Koenig in which he described writing a merge sort
function, whose type was reported (by the SML type inferencer) as [a]
-> [b], and the reason was that it had a bug that would cause it to
loop forever on any nonempty list. I came back from that conference
convinced that I must learn ML, and *Higher-Order Perl* was a direct
(although distant) outcome of that conviction.

Any discussion of the Curry-Howard isomorphism, using Haskell as an example, is somewhat fraught with trouble, because Haskell's type logic is utterly inconsistent. In addition to the examples above, in Haskell one can write

fix :: (a -> a) -> a fix f = let x = fix f in f xand as a statement of logic, is patently false. This might be an argument in favor of the Total Functional Programming suggested by D.A. Turner and others.