https://wiki.haskell.org/api.php?action=feedcontributions&user=David&feedformat=atomHaskellWiki - User contributions [en]2020-03-30T20:30:50ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Iteratee_I/O&diff=43334Iteratee I/O2011-12-03T08:25:11Z<p>David: </p>
<hr />
<div>{{Stub}}<br />
<br />
Iteratee I/O is a way to avoid the problems that can occur with lazy I/O. <br />
<br />
Discussions elsewhere on this wiki include:<br />
<br />
* [[Enumerator and iteratee]]<br />
* [[Iteratee]]<br />
<br />
Essays by Oleg:<br />
<br />
* Oleg's writings: [http://okmij.org/ftp/Streams.html#iteratee Incremental multi-level input processing with left-fold enumerator: predictable, high-performance, safe, and elegant]<br />
* [http://okmij.org/ftp/Haskell/Iteratee/Iteratee.hs An implementation by Oleg, iteratees on Chars and Strings]<br />
* [http://okmij.org/ftp/Haskell/Iteratee/IterateeM.hs A general library by Oleg] <br />
<br />
Other discussions:<br />
<br />
* [http://themonadreader.wordpress.com/2010/05/12/issue-16/ The Monad.Reader Issue 16]; see the section "Iteratee: Teaching an Old Fold New Tricks" by John W. Lato<br />
* [http://www.yesodweb.com/book/enumerator Yesod Book: Enumerator Package]<br />
* [http://sites.google.com/site/haskell/notes/lazy-io-considered-harmful-way-to-go-left-fold-enumerator Lazy IO considered harmful; way to go, Left-fold enumerator!]<br />
* [http://inmachina.net/~jwlato/haskell/iteratee/ A Darcs repository of an alternative implementation]<br />
* [http://www.scs.stanford.edu/11au-cs240h/notes/iteratee.html Stanford CS240h lecture on iteratee]<br />
<br />
Uses of Iteratee I/O:<br />
* [http://snapframework.com Snap] : The Snap web framework<br />
* [http://hackage.haskell.org/package/yaml yaml]: Low-level binding to the libyaml C library]<br />
* [http://hackage.haskell.org/package/usb-0.4 usb 0.4]: Communicate with USB devices<br />
* [http://hackage.haskell.org/package/sstable sstable]: SSTables in Haskell<br />
* [http://hackage.haskell.org/package/wai WAI]: a Web Application Interface for haskell web frameworks (used by [http://www.yesodweb.com Yesod]).<br />
<br />
Packages:<br />
* [http://hackage.haskell.org/package/iterIO iterIO] (note, that this will not compile on Windows, as it depends on the package unix)<br />
* [http://hackage.haskell.org/package/enumerator enumerator] [http://www.haskell.org/pipermail/haskell-cafe/2010-August/082324.html ANNOUNCE: enumerator, an alternative iteratee package] (this package does not use any extensions, so it will work with most Haskell compilers)<br />
* [http://hackage.haskell.org/package/attoparsec-iteratee attoparsec-iteratee]: An adapter to convert attoparsec Parsers into blazing-fast Iteratees<br />
* [http://hackage.haskell.org/package/iteratee iteratee]: Iteratee-based I/O<br />
* [http://hackage.haskell.org/package/iteratee-parsec iteratee-parsec]: Package allowing parsec parser initeratee<br />
* [http://hackage.haskell.org/package/liboleg liboleg]: An evolving collection of Oleg Kiselyov's Haskell modules (depends on the package unix and will therefore not compile on Windows systems)<br />
* See also the [http://hackage.haskell.org/packages/archive/pkg-list.html#cat:enumerator enumerator category on Hackage]<br />
<br />
[[Category:Idioms]]</div>Davidhttps://wiki.haskell.org/index.php?title=GHC.Generics&diff=40521GHC.Generics2011-06-16T06:07:19Z<p>David: </p>
<hr />
<div>GHC 7.2 includes support for ''datatype-generic programming''. This means you can have more classes for which you do not have to give an instance, like <hask>Show</hask> or <hask>Functor</hask>. This is accomplished through two new features, enabled with two new flags: <tt>DeriveGeneric</tt> and <tt>DefaultSignatures</tt>. We show how this all works in this page, starting with a detailed example.<br />
<br />
Since this is a fresh new feature, it is possible that you will run into bugs when using it. If so, please<br />
[http://hackage.haskell.org/trac/ghc/wiki/ReportABug report them]!<br />
<br />
== Example: serialization ==<br />
<br />
Suppose you are writing a class for serialization of data. You have a type <hask>Bit</hask> representing bits, and a class <hask>Serialize</hask>:<br />
<br />
<haskell><br />
data Bit = O | I<br />
<br />
class Serialize a where<br />
put :: a -> [Bit]<br />
</haskell><br />
<br />
You might have written some instances already:<br />
<br />
<haskell><br />
instance Serialize Int where<br />
put i = serializeInt i<br />
<br />
instance Serialize a => Serialize [a] where<br />
put [] = []<br />
put (h:t) = put h ++ put t<br />
</haskell><br />
<br />
A user of your library, however, will have his own datatypes, like:<br />
<br />
<haskell><br />
data UserTree a = Node a (UserTree a) (UserTree a) | Leaf<br />
</haskell><br />
<br />
He will have to specify an <hask>instance Serialize (UserTree a) where ...</hask> himself. This, however, is tedious, especially because most instances will probably be rather trivial, and should be derived automatically.<br />
<br />
It is here that generic programming can help you. If you are familiar with [http://www.cs.uu.nl/wiki/bin/view/GenericProgramming/SYB SYB] you could use it at this stage, but now we'll see how to do this with the new features of GHC 7.2.<br />
<br />
=== Generic serialization ===<br />
<br />
First you have to tell the compiler how to serialize any datatype, in general. Since Haskell datatypes have a regular structure, this means you can just explain how to serialize a few basic datatypes.<br />
<br />
==== Representation types ====<br />
<br />
We can represent most Haskell datatypes using only the following primitive types:<br />
<br />
<haskell><br />
-- | Unit: used for constructors without arguments<br />
data U1 p = U1<br />
<br />
-- | Constants, additional parameters and recursion of kind *<br />
newtype K1 i c p = K1 { unK1 :: c }<br />
<br />
-- | Meta-information (constructor names, etc.)<br />
newtype M1 i c f p = M1 { unM1 :: f p }<br />
<br />
-- | Sums: encode choice between constructors<br />
infixr 5 :+:<br />
data (:+:) f g p = L1 (f p) | R1 (g p)<br />
<br />
-- | Products: encode multiple arguments to constructors<br />
infixr 6 :*:<br />
data (:*:) f g p = f p :*: g p<br />
</haskell><br />
<br />
For starters, try to ignore the <tt>p</tt> parameter in all types; it's there just for future compatibility. The easiest way to understand how you can use these types to represent others is to see an example. Let's represent the <hask>UserTree</hask> type shown before:<br />
<br />
<haskell><br />
type RepUserTree a =<br />
-- A UserTree is either a Leaf, which has no arguments<br />
U1<br />
-- ... or it is a Node, which has three arguments that we put in a product<br />
:+: a :*: UserTree a :*: UserTree a<br />
</haskell><br />
<br />
Simple, right? Different constructors become alternatives of a sum, and multiple arguments become products. In fact, we want to have some more information in the representation, like datatype and constructor names, and to know if a product argument is a parameter or a type. We use the other primitives for this, and the representation looks more like:<br />
<br />
<haskell><br />
type RealRepUserTree a =<br />
-- Information about the datatype<br />
M1 D Data_UserTree (<br />
-- Leaf, with information about the constructor<br />
M1 C Con_Leaf U1<br />
-- Node, with information about the constructor<br />
:+: M1 C Con_Node (<br />
-- Constructor argument, which could have information<br />
-- about a record selector label<br />
M1 S NoSelector (<br />
-- Argument, tagged with P because it is a parameter<br />
K1 P a)<br />
-- Another argument, tagged with R because it is <br />
-- a recursive occurrence of a type<br />
:*: M1 S NoSelector (K1 R (UserTree a))<br />
-- Idem<br />
:*: M1 S NoSelector (K1 R (UserTree a))<br />
))<br />
</haskell><br />
<br />
A bit more complicated, but essentially the same. Datatypes like <hask>Data_UserTree</hask> are empty datatypes used only for providing meta-information in the representation; you don't have to worry much about them for now. Also, GHC generates these representations for you automatically, so you should never have to define them yourself! All of this is explained in much more detail in Section 2.1. of [http://dreixel.net/research/pdf/gdmh.pdf the original paper describing the new generic deriving mechanism].<br />
<br />
==== A generic function ====<br />
<br />
Since GHC can represent user types using only those primitive types, all you have to do is to tell GHC how to serialize each of the individual primitive types. The best way to do that is to create a new type class:<br />
<br />
<haskell><br />
class GSerialize f where<br />
gput :: f a -> [Bin]<br />
</haskell><br />
<br />
This class looks very much like the original <hask>Serialize</hask> class, just that the type argument is of kind <hask>* -> *</hask>, since our generic representation types have this <tt>p</tt> parameter lying around. Now we need to give instances for each of the basic types. For units there's nothing to serialize:<br />
<br />
<haskell><br />
instance GSerialize U1 where<br />
gput U1 = []<br />
</haskell><br />
<br />
The serialization of multiple arguments is simply the concatenation of each of the individual serializations:<br />
<br />
<haskell><br />
instance (GSerialize a, GSerialize b) => GSerialize (a :*: b) where<br />
gput (a :*: b) = gput a ++ gput b<br />
</haskell><br />
<br />
The case for sums is the most interesting, as we have to record which alternative we are in. We will use a 0 for left injections and a 1 for right injections:<br />
<br />
<haskell><br />
instance (GSerialize a, GSerialize b) => GSerialize (a :+: b) where<br />
gput (L1 x) = O : gput x<br />
gput (R1 x) = I : gput x<br />
</haskell><br />
<br />
We don't need to encode the meta-information, so we just go over it recursively :<br />
<br />
<haskell><br />
instance (GSerialize a) => GSerialize (M1 i c a) where<br />
gput (M1 x) = gput x<br />
</haskell><br />
<br />
Finally, we're only left with the arguments. For these we will just use our first class, <hask>Serialize</hask>, again:<br />
<br />
<haskell><br />
instance (Serialize a) => GSerialize (K1 i c a) where<br />
gput (K1 x) = put x<br />
</haskell><br />
[Shouldn't the context read <tt>(Serialize c)</tt> rather than <tt>(Serialize a)</tt>?]<br />
<br />
So, if a user datatype has a parameter which is instantiated to <hask>Int</hask>, at this stage we will use the library instance for <hask>Serialize Int</hask>.<br />
<br />
==== Default implementations ====<br />
<br />
We've seen how to represent user types generically, and how to define functions on representation types. However, we still have to tie these two together, explaining how to convert user types to their representation and then applying the generic function.<br />
<br />
The representation <hask>RepUserTree</hask> we have seen earlier is only one component of the representation; we also need functions to convert to and from the user datatype into the representation. For that we use another type class:<br />
<br />
<haskell><br />
class Generic a where<br />
-- Encode the representation of a user datatype<br />
type Rep a :: * -> *<br />
-- Convert from the datatype to its representation<br />
from :: a -> (Rep a) x<br />
-- Convert from the representation to the datatype<br />
to :: (Rep a) x -> a<br />
</haskell><br />
<br />
So, for the <hask>UserTree</hask> datatype shown before, GHC generates the following instance:<br />
<br />
<haskell><br />
instance Generic (UserTree a) where<br />
type Rep (UserTree a) = RepUserTree a<br />
<br />
from Leaf = L1 U1<br />
from (Node a l r) = R1 (a :*: l :*: r)<br />
<br />
to (L1 U1) = Leaf<br />
to (R1 (a :*: l :*: r)) = Node a l r<br />
</haskell><br />
<br />
(Note that we are using the simpler representation <hask>RepUserTree</hask> instead of the real representation <hask>RealRepUserTree</hask>, just for simplicity.)<br />
<br />
Equipped with a <hask>Generic</hask> instance, we are ready to tell the compiler how it can serialize any representable type:<br />
<br />
<haskell><br />
putDefault :: (Generic a, GSerialize (Rep a)) => a -> [Bit]<br />
putDefault a = gput (from a)<br />
</haskell><br />
<br />
The type of <hask>putDefault</hask> says that we can serialize any <tt>a</tt> into a list of bits, as long as that <tt>a</tt> is <hask>Generic</hask>, and its representation <hask>Rep a</hask> has a <hask>GSerialize</hask> instance. The implementation is very simple: first convert the value to its representation using <hask>from</hask>, and then call <hask>gput</hask> on that representation.<br />
<br />
However, we still have to write a <hask>Serialize</hask> instance for the user dataype:<br />
<br />
<haskell><br />
instance (Serialize a) => Serialize (UserTree a) where<br />
put = putDefault<br />
</haskell><br />
<br />
=== Using GHC's new features ===<br />
<br />
What we have seen so far could all already be done, at the cost of writing a lot of boilerplate code yourself (or spending hours writing [[Template Haskell]] code to do it for you). Now we'll see how the new features of GHC can help you.<br />
<br />
==== Deriving representations ====<br />
<br />
The <hask>Representable0</hask> class, and all the representation types, come with GHC in the <tt>GHC.Generics</tt> module. GHC can also derive <hask>Representable0</hask> for user types, so all the user has to do is:<br />
<br />
<haskell><br />
{-# LANGUAGE DeriveRepresentable #-}<br />
<br />
data UserTree a = Node a (UserTree a) (UserTree a) | Leaf<br />
deriving Representable0<br />
</haskell><br />
<br />
(Standlone deriving also works fine, and you can use it for types you have not defined yourself, but are imported from somewhere else.) You will need the new <tt>DeriveRepresentable</tt> language pragma.<br />
<br />
==== More general default methods ====<br />
<br />
We don't want the user to have to write the <hask>instance Serialize (UserTree a)</hask> himself, since most of the times it will just be <hask>putDefault</hask>. However, we cannot make <hask>putDefault</hask> the default implementation of the <hask>put</hask> method, because that would require adding the <hask>(Representable0 a, GSerialize (Rep0 a))</hask> constraint to the class head. This would restrict the ability to give ad-hoc instances for types that are not representable, for instance.<br />
<br />
We solved this by allowing the user to give a different signature for default methods:<br />
<br />
<haskell><br />
{-# LANGUAGE DefaultSignatures #-}<br />
<br />
class Serialize a where<br />
put :: a -> [Bit]<br />
<br />
default put :: (Representable0 a, GSerialize (Rep0 a)) => a -> [Bit]<br />
put a = gput (from0 a)<br />
</haskell><br />
<br />
With the new language pragma <tt>DefaultSignatures</tt>, GHC allows you to put the keyword <hask>default</hask> before a (new) type signature for a method inside a class declaration. If you give such a default type signature, then you have to provide a default method implementation, which will be type-checked using the default signature, and not the original one.<br />
<br />
Now the user can simply write:<br />
<br />
<haskell><br />
instance (Serialize a) => Serialize (UserTree a)<br />
</haskell><br />
<br />
GHC fills out the implementation for <hask>put</hask> using the default method. It will type-check correctly because we have a <hask>Representable0</hask> instance for <hask>UserTree</hask>, and <hask>GSerialize</hask> instances for all the representation types.<br />
<br />
== Different perspectives ==<br />
<br />
We outline the changes introduced in 7.2 regarding support for generic programming from the perspective of three different types of users: the end-user, the generic programmer, and the GHC hacker.<br />
<br />
=== The end-user ===<br />
<br />
If you know nothing about generic programming and would like to keep it that way, then you will be pleased to know that using generics in GHC 7.2 is easier than ever. As soon as you encounter a class with a default signature (like <tt>Serialize</tt> above), you will be able to give empty instances for your datatypes, like this:<br />
<br />
<haskell><br />
instance (Serialize a) => Serialize (UserTree a)<br />
</haskell><br />
<br />
You will need to add a <hask>deriving Generic</hask> clause to each datatype that you want to have generic implementations for. You might have datatypes that use other datatypes, and you might need <tt>Generic</tt> instances for those too. In that case, you can import the module where the datatype is defined and give a standalone deriving <tt>Generic</tt> instance. In either case, you will need the <tt>-XDeriveGeneric</tt> flag.<br />
<br />
=== The generic programmer ===<br />
<br />
If you are a library author and are eager to make your classes easy to instantiate by your users, then you should invest some time in defining instances for each of the representation types of <tt>GHC.Generics</tt> and defining a generic default method. See the example for <tt>Serialize</tt> above, and the [http://dreixel.net/research/pdf/gdmh.pdf original paper] for many other examples (but make sure to check the [[Generics#Changes from the paper|changes from the paper]]).<br />
<br />
=== The GHC hacker ===<br />
<br />
If you are working on the GHC source code, you might find it useful to know what kind of changes were made. There is a [http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/GenericDeriving Trac wiki page] with a lower-level overview of things and also keeping track of what still needs to be done.<br />
<br />
== Changes from the paper ==<br />
<br />
In the [http://dreixel.net/research/pdf/gdmh.pdf paper] we describe the implementation in [http://www.cs.uu.nl/wiki/UHC UHC]. The implementation in GHC is slightly different:<br />
<br />
* <tt>Representable0</tt> and <tt>Representable1</tt> have become <tt>Generic</tt> and <tt>Generic1</tt>, respectively. <tt>from0</tt>, <tt>to0</tt>, and <tt>Rep0</tt> also lost the <tt>0</tt> at the end of their names.<br />
<br />
* We are using type families, so the <tt>Generic</tt> and <tt>Generic1</tt> type classes have only one type argument. So, in GHC the classes look like what we describe in the "Avoiding extensions" part of Section 2.3 of the paper. This change affects only a generic function writer, and not a generic function user.<br />
<br />
* Default definitions (Section 3.3) work differently. In GHC we don't use a <tt>DERIVABLE</tt> pragma; instead, a type class can declare a ''generic default method'', which is akin to a standard default method, but includes a default type signature. This removes the need for a separate default definition and a pragma. For example, the <tt>Encode</tt> class of Section 3.1 is now:<br />
<haskell><br />
class Encode a where<br />
encode :: a -> [Bit]<br />
default encode :: (Generic a, Encode1 (Rep a)) => a -> [Bit]<br />
encode = encode1 . from<br />
</haskell><br />
<br />
* To derive generic functionality to a user type, the user no longer uses <hask>deriving instance</hask> (Section 4.6.1). Instead, the user gives an instance without defining the method; GHC then uses the generic default. For instance:<br />
<haskell><br />
instance Encode [a] -- works if there is an instance Generic [a]<br />
</haskell><br />
<br />
== Limitations ==<br />
<br />
* We do not yet allow <hask>deriving Generic1</hask> clauses. This means that functions like <tt>fmap</tt> cannot be easily expressed generically in GHC yet.<br />
<br />
* We cannot derive <tt>Generic</tt> instances for:<br />
** Datatypes with a context;<br />
** Existentially-quantified datatypes;<br />
** GADTs.<br />
<br />
<br />
[[Category:GHC]]<br />
[[Category:Language extensions]]</div>Davidhttps://wiki.haskell.org/index.php?title=Scoped_type_variables&diff=30094Scoped type variables2009-09-18T03:23:07Z<p>David: use LANGUAGE rather than OPTIONS_GHC pragma</p>
<hr />
<div>Scoped Type Variables are an extension to Haskell's type system that allow free type variables to be re-used in the scope of a function. They are also described in the [http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#scoped-type-variables GHC documentation].<br />
<br />
As an example, consider the following functions:<br />
<br />
<haskell><br />
{-# LANGUAGE ScopedTypeVariables #-}<br />
<br />
...<br />
<br />
mkpair1 :: forall a b. a -> b -> (a,b)<br />
mkpair1 aa bb = (ida aa, bb)<br />
where<br />
ida :: a -> a -- This refers to a in the function's type signature<br />
ida = id<br />
<br />
mkpair2 :: forall a b. a -> b -> (a,b)<br />
mkpair2 aa bb = (ida aa, bb)<br />
where<br />
ida :: b -> b -- Illegal, because refers to b in type signature<br />
ida = id<br />
<br />
mkpair3 :: a -> b -> (a,b)<br />
mkpair3 aa bb = (ida aa, bb)<br />
where<br />
ida :: b -> b -- Legal, because b is now a free variable<br />
ida = id<br />
</haskell><br />
<br />
Scoped type variables make it possible to specify the particular type of a function in situations where it is not otherwise possible, which can in turn help avoid problems with the [[Monomorphism_restriction]].<br />
<br />
This feature should be better documented in the Wiki, but this is a start.</div>Davidhttps://wiki.haskell.org/index.php?title=Scoped_type_variables&diff=29534Scoped type variables2009-08-13T06:36:08Z<p>David: </p>
<hr />
<div>Scoped Type Variables are an extension to Haskell's type system that allow free type variables to be re-used in the scope of a function. They are also described in the [http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#scoped-type-variables GHC documentation].<br />
<br />
As an example, consider the following functions:<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -XScopedTypeVariables #-}<br />
<br />
...<br />
<br />
mkpair1 :: forall a b. a -> b -> (a,b)<br />
mkpair1 aa bb = (ida aa, bb)<br />
where<br />
ida :: a -> a -- This refers to a in the function's type signature<br />
ida = id<br />
<br />
mkpair2 :: forall a b. a -> b -> (a,b)<br />
mkpair2 aa bb = (ida aa, bb)<br />
where<br />
ida :: b -> b -- Illegal, because refers to b in type signature<br />
ida = id<br />
<br />
mkpair3 :: a -> b -> (a,b)<br />
mkpair3 aa bb = (ida aa, bb)<br />
where<br />
ida :: b -> b -- Legal, because b is now a free variable<br />
ida = id<br />
</haskell><br />
<br />
Scoped type variables make it possible to specify the particular type of a function in situations where it is not otherwise possible, which can in turn help avoid problems with the [[Monomorphism_restriction]].<br />
<br />
This feature should be better documented in the Wiki, but this is a start.</div>Davidhttps://wiki.haskell.org/index.php?title=Scoped_type_variables&diff=29533Scoped type variables2009-08-13T01:39:19Z<p>David: </p>
<hr />
<div>Scoped Type Variables are an extension to Haskell's type system that allow free type variables to be re-used in the scope of a function. The are also described in the [http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#scoped-type-variables GHC documentation].<br />
<br />
As an example, consider the following functions:<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -XScopedTypeVariables #-}<br />
<br />
...<br />
<br />
mkpair1 :: forall a b. a -> b -> (a,b)<br />
mkpair1 aa bb = (ida aa, bb)<br />
where<br />
ida :: a -> a -- This refers to a in the function's type signature<br />
ida = id<br />
<br />
mkpair2 :: forall a b. a -> b -> (a,b)<br />
mkpair2 aa bb = (ida aa, bb)<br />
where<br />
ida :: b -> b -- Illegal, because refers to b in type signature<br />
ida = id<br />
<br />
mkpair3 :: a -> b -> (a,b)<br />
mkpair3 aa bb = (ida aa, bb)<br />
where<br />
ida :: b -> b -- Legal, because b is now a free variable<br />
ida = id<br />
</haskell><br />
<br />
Scoped type variables make it possible to specify the particular type of a function in situations where it is not otherwise possible, which can in turn help avoid problems with the [[Monomorphism_restriction]].<br />
<br />
This feature should be better documented in the Wiki, but this is a start.</div>David