https://wiki.haskell.org/api.php?action=feedcontributions&user=RichardSmith&feedformat=atomHaskellWiki - User contributions [en]2024-03-19T04:58:12ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=AngloHaskell/2010&diff=36578AngloHaskell/20102010-08-27T09:55:36Z<p>RichardSmith: </p>
<hr />
<div>AngloHaskell 2010 is taking place on the 10th and 11th of September in Cambridge, UK (yes, tradition has been broken and month has changed!). It's free, and everyone is invited! Simply add your name to the wiki and we'll see you there.<br />
<br />
Organisational contact: Derek Wright<br />
<br />
== Dates and Venues ==<br />
<br />
{| class="wikitable"<br />
|-<br />
! Date !! Venue<br />
|-<br />
| Friday 10th September || Microsoft Research, Cambridge, UK<br />
|-<br />
| Saturday 11th September || A less formal venue (to be organised, any suggestions?)<br />
|}<br />
<br />
== Attendees ==<br />
<br />
Per last year, all attendees should '''bring or make a nametag''' that identifies you by your real name and/or IRC name. If anyone wants to drag a roll of stickers and a pen along that'll help!<br />
<br />
If you can't make the start on Friday, or can only make it on Saturday, that's fine. If you're not sure where everyone's going to be, give one of the contacts a call or a text.<br />
<br />
=== Definite ===<br />
<br />
* Derek Wright (Fri + Sat)<br />
* Graeme Burnett (Fri + Sat)<br />
* Neil Mitchell (hopefully Fri, definite Sat)<br />
* Sam Martin (Fri but not Sat)<br />
* Eric Kow (Fri + Sat)<br />
* Richard Smith (Fri only)<br />
* Add your name here<br />
<br />
=== Possible ===<br />
<br />
* Claude Heiland-Allen<br />
* Joshua Lee Tucker<br />
* Ben May<br />
* Alex McLean (hopefully Fri, can't do Sat)<br />
* Magnus Therning<br />
* Richard Fergie (just Friday)<br />
* Benedict Eastaugh<br />
* Max Bolingbroke<br />
* Roland Swingler<br />
* Add your name here<br />
<br />
== Lodging ==<br />
<br />
It's likely that there'll be people in need of crashspace and so forth, so please organise here! Both offers and requests are good.<br />
<br />
=== Hostels ===<br />
<br />
Details coming soon...<br />
<br />
== Programme ==<br />
<br />
Planning will be taking place on IRC as per previous years: #anglohaskell on irc.freenode.net<br />
<br />
If you're having trouble following things on IRC, the discussion page on the wiki might be a good place to leave comments and questions.<br />
<br />
In previous years we had talks in the day on a Friday, followed by pubbage in the evening and assorted activities on the Saturday. This seemed to work, so we'll follow a similar model this year.<br />
<br />
=== Timetable ===<br />
<br />
This is somewhat preliminary and subject to change as talks are confirmed or otherwise, but the overall structure should hold: <br />
<br />
{| class="wikitable"<br />
|-<br />
! Day !! Time !! Event<br />
|-<br />
| Friday or Saturday || 10am || People start arriving<br />
|-<br />
| || 10:30 am || Tea, coffee and biscuits<br />
|-<br />
| || 11am || Talks<br />
|-<br />
| || 1pm || Lunch<br />
|-<br />
| || 2pm || More talks<br />
|-<br />
| || 3:30pm || Tea, coffee and biscuits<br />
|-<br />
| || 4pm || Remaining talks<br />
|-<br />
| || 4:??pm || Functional Grit - small talks that may grow into functional pearls. Open session, anyone can give a quick talk!<br />
|-<br />
| || When people get hungry or the venue kicks us out || Food! Likely we'll head out for a curry<br />
|-<br />
| || Beer o'Clock || When everyone's finished eating, we'll head for a nearby pub<br />
|-<br />
| 2nd Day || To be confirmed<br />
|}<br />
<br />
=== Talks ===<br />
<br />
Volunteers please! Previously we have had a largely more practical set of talks than you might find at Fun in the Afternoon or an academic event. This was a good thing, and some of the best talks were from people who were far from considering themselves as experts, so feel free to tell us about your experiences.<br />
<br />
Talks planned and/or offered:<br />
<br />
* Claude Heiland-Allen - "mandulia: A zooming visualisation of the Mandelbrot Set as many Julia Sets"<br />
* Alex McLean - "tidal - live coding patterns with Haskell"<br />
* Add your name here - Add your title here<br />
<br />
==== Abstracts ====<br />
<br />
People giving talks should add these as they have them :-)<br />
<br />
* [http://hackage.haskell.org/package/mandulia-0.4 mandulia: A zooming visualisation of the Mandelbrot Set as many Julia Sets]<br />
<br />
Mandulia provides a zooming visualisation of the Mandelbrot Set as many Julia Sets. Featuring a profiled and optimized renderer, and a Lua configuration and scripting interface. <br />
<br />
* Title here<br />
<br />
abstract goes here<br />
<br />
==== Functional Grit ====<br />
<br />
In previous years there has been a successful 'functional grit' section. Usually an informal session for people to briefly talk/demo works in progress, no need to pre-register, just turn up and talk. Think small stones that might turn into functional pearls. If there's time it'd be great to do again this year.<br />
<br />
=== Other activity ===<br />
<br />
After Friday's talks, food and drink would be a good idea! Curry is traditional and probably the default, but we're open to other suggestions. After that, we'll retreat to a pub for the evening.<br />
<br />
<br />
[[User:DWright|Derek Wright]]<br />
<br />
[[Category:Events]]</div>RichardSmithhttps://wiki.haskell.org/index.php?title=AngloHaskell/2009&diff=29367AngloHaskell/20092009-07-31T12:25:05Z<p>RichardSmith: </p>
<hr />
<div>AngloHaskell 2009 is taking place on the 7th of August at MSR Cambridge, with further activities on the 8th. It's free, and everyone is invited! Simply add your name to the wiki and we'll see you there :-)<br />
<br />
Organisational contact: Neil Mitchell, 07876 126 574. If you are lost or confused just give Neil a ring. If Neil's phone is busy, you can also drop Sam Martin a line on 07947 249 476. If you need help when you arrive at the train station, [[User:Peter McArthur|Peter McArthur]] (07804 596282) lives just nearby.<br />
<br />
We're still looking for people willing to put someone up for the night (even if on a floor) would also be much appreciated. Any volunteers?<br />
<br />
== Date and Venue ==<br />
<br />
7th-8th of August in Cambridge, UK, starting with talks at Microsoft Research and with more planning to happen below.<br />
<br />
=== Directions to MSR ===<br />
<br />
MSR has [http://research.microsoft.com/aboutmsr/visitmsr/cambridge/directions.aspx some directions], which can be best summarised as ‘get a taxi’. Here is (hopefully) a [http://earth.google.com/ Google Earth] [[Media:Microsoft_Research,_Cambridge.kmz|location]] of MSR, as well as a [http://maps.google.com/maps?q=CB3+0FB&ll=52.211499,0.117073&spn=0.02677,0.086517 Google Maps link]. (J J Thomson Avenue is immediately west of Clerk Maxwell Road.)<br />
<br />
If the weather is co-operative, the best way to get around Cambridge is by bike. If you're bringing a bike, you could ask [[User:Peter McArthur|Peter McArthur]] to be your guide.<br />
<br />
If you do take a taxi and the driver doesn't know where it is, tell him or her to drive down Madingley Road until you reach the West Cambridge site, J J Thomson Avenue. The Computer Laboratory (next door) has [http://www.cl.cam.ac.uk/UoCCL/contacts/#gettinghere marginally better instructions].<br />
<br />
The fastest way to MSR (on foot and public transport) from the station is to [http://maps.google.com/maps?saddr=CB1+2JW&daddr=Trumpington+Road,+Cambridge cut through to Trumpington Road via Bateman Street] (don't follow the driving directions!), and take the Citi 4 or Uni 4. There's a bus stop just across the road from Bateman Street.<br />
<br />
To get to the city centre by bus, take the Citi 1 or Citi 3. Do ask to make sure they're going in the right direction though! There are also a number of clearly marked shuttle busses between the centre and station running during the day every 10 minutes or so.<br />
<br />
To walk to the centre (20 minutes not carrying luggage), go straight down the road facing you when you come out of the station, bear right when the road ends at some traffic lights / a WW1 memorial / the botanic gardens, and keep walking straight (Hills Road / Regent St / St Andrews St) for quite a while until you reach a pedestrianised bit, at which point you are in the centre.<br />
<br />
From the city centre to MSR, you can catch the number 77 Madingley Road Park and Ride which goes from bus stop M on Emma St. (Or find your way to Pembroke or Silver Street, and catch the Citi 4 / Uni 4 from there.) (Note that the 77 doesn't stop by MSR any more, it goes to the park and ride from which you have to walk back, 10-15 mins. This caught me out the other day --SimonM)<br />
<br />
==== Parking ====<br />
<br />
To be verified:<br />
<br />
Some parking spaces will be available around the back of the MSR building. To get out again, drivers will need to talk to reception to obtain a token.<br />
<br />
== Attendees ==<br />
<br />
Per last year, all attendees should '''bring or make a nametag''' that identifies you by your real name and/or IRC name. If anyone wants to drag a roll of stickers and a pen along that'll help!<br />
<br />
If you can't make the start on Friday, or can only make it on Saturday, that's fine. If you're not sure where everyone's going to be, give one of the contacts a call or a text.<br />
<br />
=== Definite ===<br />
<br />
* Philippa Cowderoy<br />
* Neil Mitchell<br />
* Eric Kow<br />
* Tom Schrijvers<br />
* Eric Macaulay<br />
* Peter McArthur<br />
* Tristan Allwood (Friday only)<br />
* Neil Brown (Friday only)<br />
* Sam Martin<br />
* Thomas Schilling<br />
* Edwin Brady<br />
* Tony Cowderoy<br />
* Ashley Moran<br />
* Richard Smith<br />
* Tom Ellis<br />
<br />
=== Possible ===<br />
<br />
* Lennart Augustsson<br />
* Magnus Therning<br />
* Michael Dever (Travelling over from Ireland, so if anyone else is going, get in touch :) )<br />
* Ganesh Sittampalam<br />
* Cal Paterson<br />
* Jón Fairbairn (probably only Friday afternoon)<br />
* Michael Furniss<br />
* James Rowe (Friday only)<br />
* Richard Barrell<br />
* Jon Pretty<br />
<br />
=== Wifi signup ===<br />
<br />
Wifi accounts are available on request. The signup deadline's the 31st of July. Everyone wanting an account should provide:<br />
<br />
* Full name<br />
* Institution<br />
* Country of residence<br />
* email address<br />
<br />
'''Signups here:'''<br />
<br />
If you'd prefer not to give details here, please email Philippa at ''flippa at flippac dot org'' with the subject "Wifi signup".<br />
<br />
* Philippa Cowderoy, flippac.org, UK, flippa at flippac dot org<br />
* Ganesh Sittampalam, Credit Suisse, UK, ganesh.sittampalam@credit-suisse.com<br />
* Neil Brown, University of Kent, UK, nccb2@kent.ac.uk<br />
* Eric Kow, University of Brighton, UK, kowey at darcs dot net<br />
* Peter McArthur, dysfunctor.org, UK, peter dot mcarthur at gmail dot com<br />
* Tristan Allwood, Imperial College, UK, tora@zonetora.co.uk<br />
* Edwin Brady, University of St Andrews, UK, eb@cs.st-and.ac.uk<br />
* Tony Cowderoy, MML, UK, tony dot cowderoy at mml-net dot com<br />
* Richard Barrell, ???, UK, mycatverbs at gmail dot com.<br />
<br />
== Lodging ==<br />
<br />
It's likely that there'll be people in need of crashspace and so forth, so please organise here! Both offers and requests are good.<br />
<br />
* I live in a studio flat near the station. I could accommodate one person, but if you value your personal space or privacy then this isn't the place for you. [[User:Peter McArthur|Peter McArthur]]<br />
<br />
=== Nearby Colleges ===<br />
<br />
Many of undergraduate colleges offer cheap accommodation over the holidays. Locations near MSR include Churchill College, Wolfson Court (an annexe of Girton College), Fitzwillian College, Robinson College, <del>New Hall</del> <ins>Murray Edwards</ins> (female only; recently renamed) and Burwells Field (an annexe of Trinity College). ([http://www.cam.ac.uk/map/v4/drawmap.cgi?mp=main;xx=900;yy=560;mt=c;mx=759;my=467;ms=75;tl=Microsoft%20Research This map] might prove useful.)<br />
<br />
=== Hostels ===<br />
<br />
There's a fairly inexpensive [http://www.yha.org.uk/find-accommodation/east-of-england/hostels/cambridge/index.aspx YHA hostel] in Cambridge.<br />
<br />
Another guest house right next to the station is Tenison Towers (01223 363924).<br />
<br />
== Programme ==<br />
<br />
Planning will be taking place on IRC as per previous years: #anglohaskell on irc.freenode.net<br />
<br />
If you're having trouble following things on IRC, the discussion page on the wiki might be a good place to leave comments and questions.<br />
<br />
Previous years in Cambridge we had talks in the day on a Friday, followed by pubbage in the evening and assorted activities on the Saturday. This seemed to work, so we'll follow a similar model this year. Sadly we can't have talk space at MSR on a Saturday.<br />
<br />
=== Timetable ===<br />
<br />
This is somewhat preliminary and subject to change as talks are confirmed or otherwise, but the overall structure should hold: <br />
<br />
{| class="wikitable"<br />
|-<br />
! Day !! Time !! Event<br />
|-<br />
| Friday || 10am || People start arriving at MS Research<br />
|-<br />
| || 10:30 am || Tea, coffee and biscuits<br />
|-<br />
| || 11am || Keynote<br />
|-<br />
| || shortly after || Talk 1<br />
|-<br />
| || ~11:30 pm || Talk 2<br />
|-<br />
| || ~12:00 pm || Talk 3<br />
|-<br />
| || ~12:30 pm || Talk 4<br />
|-<br />
| || 1pm || Lunch<br />
|-<br />
| || 2pm || Future of Anglohaskell<br />
|-<br />
| || 2:??pm || More talks<br />
|-<br />
| || 3:30pm || Tea, coffee and biscuits<br />
|-<br />
| || 4pm || Remaining talks<br />
|-<br />
| || 4:??pm || Functional Grit - small talks that may grow into functional pearls. Open session, anyone can give a quick talk!<br />
|-<br />
| || When people get hungry or MSR kick us out || Food! Likely we'll head out for a curry<br />
|-<br />
| || Beer o'Clock || When everyone's finished eating, we'll head for a nearby pub<br />
|-<br />
| Saturday || 11am || Brunch, chat and impromptu hacking at [http://www.beerintheevening.com/pubs/s/13/1361/Regal/Cambridge The Regal] - at least someone will stay on until 1pm, next activity may start earlier though, anyone who may show up late should keep phone numbers for one or more of the contacts<br />
|-<br />
| || 1pm || Afternoon activities - probably punting if it's not raining, failing that we'll find something<br />
|-<br />
| || When everyone gets tired/hungry || We'll retire to a pub for food, drink, chat and perhaps hacking. A pub with wifi'll be preferred, so feel free to bring a laptop or PDA!<br />
|}<br />
<br />
=== Talks ===<br />
<br />
Volunteers please! Previously we have had a largely more practical set of talks than you might find at Fun in the Afternoon or an academic event. This was a good thing, and some of the best talks were from people who were far from considering themselves as experts, so feel free to tell us about your experiences.<br />
<br />
In the event that more talks are offered than we have time for at MSR, we'll have to work out what we can do to find more time.<br />
<br />
Talks planned and/or offered:<br />
<br />
* Neil Mitchell - hopefully "Make Considered Harmful"<br />
* Tom Schrijvers - "Monadic Constraint Programming"<br />
* Tristan Allwood - "Using the GHC API to automatically find errors"<br />
* Neil Brown - "CSP Models on the Cheap" (like several others, I spoke last year -- so others should have priority if we get too many talks)<br />
* Sam Martin - "Functional languages in games development: plotting the coup"<br />
<br />
==== Abstracts ====<br />
<br />
People giving talks should add these as they have them :-)<br />
<br />
* Monadic Constraint Programming<br />
<br />
A constraint programming system combines two essential components: a constraint solver and a search engine. The constraint solver reasons about satisfiability of conjunctions of constraints, and the search engine controls the search for solutions by iteratively exploring a disjunctive search tree defined by the constraint program.<br />
<br />
The Monadic Constraint Programming framework gives a monadic definition of constraint programming where the solver is defined as a monad threaded through the monadic search tree. Search and search strategies can then be defined as first-class objects that can themselves be built or extended by composable search transformers. Search transformers give a powerful and unifying approach to viewing search in constraint programming, and the resulting constraint programming system is first class and extremely flexible. <br />
<br />
* CSP Models on the Cheap<br />
<br />
Hoare's Communicating Sequential Processes and the model-checker FDR provide a way to check implementations of concurrent programs against formal specifications and also to check for deadlock-freedom. The Communicating Haskell Processes (CHP) library already provides a way to implement CSP-style message-passing concurrency in Haskell using a CHP monad. In this talk, I discuss substituting the definition of the CHP monad for one that emits a formal model of the program, never requiring the full program to be executed and bypassing the need for source code analysis. This model can then be checked for deadlock or refinement of a specification. I will explain how several features of Haskell make this work possible, particularly monads, purity and lazy evaluation.<br />
<br />
* Make Considered Harmful<br />
<br />
The hardest part when writing a compiler for a functional language seems to be the make system - how to compile the compiler. GHC has rewritten its build system from scratch at least 3 times. Yhc died under 10,000 lines of Python Scons scripts. There have been many alternatives to make proposed (SCons, CMake ...) but none of them seem to work as well as one might hope. This talk discusses an alternative approach, writing a make system as a Haskell program with a suitable make library providing a convenient DSL. Practical experience suggests that this approach is the only sensible choice for a build system.<br />
<br />
* Functional languages in games development: plotting the coup<br />
<br />
As a games developer by trade, my experience of the industry leads me to suspect games development is approaching a tipping point where functional languages could enact a successful coup. The revolution would claim a chunk of C++-owned territory for the victor and mark an important milestone in the development of functional languages. It will not be easy. Games development is notoriously demanding and the successful functional language would need to meet stringent performance requirements, have clearly demonstrable 'killer apps', jump through hoops of fire and tell jokes at parties. This talk will discuss how close Haskell is to meeting these demands, the challenges that remain, evidence of functional languages already in games, and how Haskell compares against its nearest competitors.<br />
<br />
==== Functional Grit ====<br />
<br />
In previous years there has been a successful 'functional grit' section. Usually an informal session for people to briefly talk/demo works in progress, no need to pre-register, just turn up and talk. Think small stones that might turn into functional pearls. If there's time it'd be great to do again this year.<br />
<br />
=== Future of Anglohaskell ===<br />
<br />
In previous years there's not really been much of a plan - the first year was classic benevolent opportunism when the GHC maintainer interviews brought a number of people together, and then someone offered to run the next year in the pub each year. There was a bit of a hiccup this year. At the same time, four years starts to seem like tradition. Time to work out what the tradition should really be, no?<br />
<br />
Rather than a talk, this'll be a discussion session. Any and all ideas welcome. Organisers for future years doubly so!<br />
<br />
=== Other activity ===<br />
<br />
After Friday's talks, food and drink would be a good idea! Curry is traditional and probably the default, but we're open to other suggestions. After that, we'll retreat to a pub for the evening.<br />
<br />
Repeating previous years, I suggest we go to [http://www.beerintheevening.com/pubs/s/13/1361/Regal/Cambridge The Regal] for brunch on Saturday to kick off with. That's the Wetherspoons from previous years. After that, punting again if it's not raining too much? Any suggestions for if it's wet?<br />
<br />
[[User:PhilippaCowderoy|PhilippaCowderoy]]<br />
<br />
[[Category:Events]]</div>RichardSmithhttps://wiki.haskell.org/index.php?title=Foldable_and_Traversable&diff=28813Foldable and Traversable2009-07-01T09:10:33Z<p>RichardSmith: fmap and toList must commute [fmap can't change the structure and toList's order can't depend on the values]</p>
<hr />
<div>[[Category:Code]] [[Category:Idioms]]<br />
<br />
<center>'''Notes on Foldable, Traversable and other useful classes'''</center><br />
<center>'' or "Where is Data.Sequence.toList?"''</center><br />
<br />
[http://haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html Data.Sequence] is recommended as an efficient alternative to [list]s,<br />
with a more symmetric feel and better complexity on various<br />
operations.<br />
<br />
When you've been using it for a little while, there seem to be some<br />
baffling omissions from the API. The first couple you are likely to<br />
notice are the absence of "<hask>map</hask>" and "<hask>toList</hask>".<br />
<br />
The answer to these lies in the long list of instances which Sequence<br />
has. The Sequence version of map is "<hask>fmap</hask>", which comes from the<br />
Functor class. The Sequence version of <hask>toList</hask> is in the <hask>Foldable</hask> [[class]].<br />
<br />
When working with <hask>Sequence</hask> you also want to refer to the documentation<br />
for at least <hask>Foldable</hask> and <hask>Traversable</hask>. <hask>Functor</hask> only has the single<br />
[[method]], so we've already covered that.<br />
<br />
==What do these classes all mean? A brief tour:==<br />
<br />
[[Image:FunctorHierarchy.svg]]<br />
<br />
===<hask>Functor</hask>===<br />
<br />
A [[functor]] is simply a [[container]]. Given a container, and a [[function]]<br />
which works on the elements, we can apply that function to each<br />
element. For lists, the familiar "<hask>map</hask>" does exactly this.<br />
<br />
Note that the function can produce elements of a different [[type]], so we<br />
may have a different type at the end.<br />
<br />
Examples:<br />
<br />
<haskell><br />
Prelude Data.Sequence> map (\n -> replicate n 'a') [1,3,5]<br />
["a","aaa","aaaaa"]<br />
Prelude Data.Sequence> fmap (\n -> replicate n 'a') (1 <| 3 <| 5 <| empty)<br />
fromList ["a","aaa","aaaaa"]<br />
</haskell><br />
<br />
===Foldable===<br />
<br />
A <hask>Foldable</hask> [[type]] is also a [[container]] (although the [[class]] does not<br />
technically require <hask>Functor</hask>, interesting <hask>Foldable</hask>s are all <hask>Functor</hask>s). It is a container with the added property that its items<br />
can be 'folded' to a summary value. In other words, it is a type which<br />
supports "<hask>foldr</hask>".<br />
<br />
Once you support <hask>foldr</hask>, of course, you can be turned into a list, by<br />
using <hask>toList = foldr (:) []</hask>. This means that all <hask>Foldable</hask>s have a<br />
representation as a list, but the order of the items may or may<br />
not have any particular significance. However, if a <hask>Foldable</hask> is<br />
also a <hask>Functor</hask>, [[parametricity]] and the [[Functor law]] guarantee that <hask>toList</hask> and <hask>fmap</hask> commute. Further, in the case of <hask>Data.Sequence</hask>, there '''is''' a well defined order and it is exposed as expected by <hask>toList</hask>.<br />
<br />
A particular kind of fold well-used by Haskell programmers is<br />
<hask>mapM_</hask>, which is a kind of fold over<br />
<hask>(>>)</hask>, and <hask>Foldable</hask> provides this along with the<br />
related <hask>sequence_</hask>.<br />
<br />
===Traversable===<br />
<br />
A <hask>Traversable</hask> [[type]] is a kind of upgraded <hask>Foldable</hask>. Where <hask>Foldable</hask><br />
gives you the ability to go through the structure processing the<br />
elements (<hask>foldr</hask>) but throwing away the shape, <hask>Traversable</hask> allows you<br />
to do that whilst preserving the shape and, e.g., putting new values<br />
in.<br />
<br />
<hask>Traversable</hask> is what we need for <hask>mapM</hask> and<br />
<hask>sequence</hask> : note the apparently surprising fact that the<br />
"_" versions are in a different [[typeclass]].<br />
<br />
== Some trickier functions: concatMap and filter ==<br />
<br />
Neither <hask>Traversable</hask> nor <hask>Foldable</hask> contain elements for <hask>concatMap</hask> and <hask>filter</hask>. That is because <hask>Foldable</hask> is about tearing down the structure<br />
completely, while <hask>Traversable</hask> is about preserving the structure<br />
exactly as-is. On the other hand <hask>concatMap</hask> tries to<br />
'squeeze more elements in' at a place and <hask>filter</hask> tries to<br />
cut them out.<br />
<br />
You can write <hask>concatMap</hask> for <hask>Sequence</hask> as follows:<br />
<br />
<haskell><br />
concatMap :: (a -> Seq b) -> Seq a -> Seq b<br />
concatMap = foldMap<br />
</haskell><br />
<br />
But why does it work? It works because sequence is an instance of<hask>Monoid</hask>, where the [[monoid]]al operation is "appending". The same<br />
definition works for lists, and we can write it more generally as:<br />
<br />
<haskell><br />
concatMap :: (Foldable f, Monoid (f b)) => (a -> f b) -> f a -> f b<br />
concatMap = foldMap<br />
</haskell><br />
<br />
And that works with lists and sequences both. Does it work with any<br />
Monoid which is Foldable? Only if the Monoid 'means the right<br />
thing'. If you have <hask>toList (f `mappend` g) = toList f ++ toList g</hask> then it definitely makes sense. In fact this easy to write<br />
condition is stronger than needed; it would be good enough if they<br />
were permutations of each other.<br />
<br />
<hask>filter</hask> turns out to be slightly harder still. You need<br />
something like 'singleton' (from <hask>Sequence</hask>), or <hask>\a -> [a]</hask><br />
for lists. We can use <hask>pure</hask> from <hask>Applicative</hask>, although<br />
it's not really right to bring <hask>Applicative</hask> in for this, and get:<br />
<br />
<haskell><br />
filter :: (Applicative f, Foldable f, Monoid (f a)) => <br />
(a -> Bool) -> f a -> f a<br />
filter p = foldMap (\a -> if p a then pure a else mempty)<br />
</haskell><br />
<br />
It's interesting to note that, under these conditions, we have a candidate<br />
to help us turn the <hask>Foldable</hask> into a <hask>Monad</hask>, since <hask>concatMap</hask> is a good<br />
definition for <hask>>>=</hask>, and we can use <hask>pure</hask> for <hask>return</hask>.<br />
<br />
== Generalising zipWith ==<br />
<br />
Another really useful list [[combinator]] that doesn't appear in the<br />
interfaces for <hask>Sequence</hask>, <hask>Foldable</hask> or <hask>Traversable</hask> is <hask>zipWith</hask>. The most general kind of <hask>zipWith</hask> over <hask>Traversable</hask>s will keep the exact shape of<br />
the <hask>Traversable</hask> on the left, whilst zipping against the values on the right. It turns out you can get away with a <hask>Foldable</hask> on the right, but you need to use a <hask>Monad</hask> (or an <hask>Applicative</hask>, actually) to thread the<br />
values through:<br />
<br />
<haskell><br />
import Prelude hiding (sequence)<br />
<br />
import Data.Sequence<br />
import Data.Foldable<br />
import Data.Traversable<br />
import Control.Applicative<br />
<br />
<br />
data Supply s v = Supply { unSupply :: [s] -> ([s],v) }<br />
<br />
instance Functor (Supply s) where <br />
fmap f av = Supply (\l -> let (l',v) = unSupply av l in (l',f v))<br />
<br />
instance Applicative (Supply s) where<br />
pure v = Supply (\l -> (l,v))<br />
af <*> av = Supply (\l -> let (l',f) = unSupply af l<br />
(l'',v) = unSupply av l'<br />
in (l'',f v))<br />
<br />
runSupply :: (Supply s v) -> [s] -> v<br />
runSupply av l = snd $ unSupply av l<br />
<br />
supply :: Supply s s<br />
supply = Supply (\(x:xs) -> (xs,x))<br />
<br />
zipTF :: (Traversable t, Foldable f) => t a -> f b -> t (a,b)<br />
zipTF t f = runSupply (traverse (\a -> (,) a <$> supply) t) (toList f)<br />
<br />
zipWithTF :: (Traversable t,Foldable f) => (a -> b -> c) -> t a -> f b -> t c<br />
zipWithTF g t f = runSupply (traverse (\a -> g a <$> supply) t) (toList f)<br />
<br />
zipWithTFM :: (Traversable t,Foldable f,Monad m) => <br />
(a -> b -> m c) -> t a -> f b -> m (t c)<br />
zipWithTFM g t f = sequence (zipWithTF g t f)<br />
<br />
zipWithTFA :: (Traversable t,Foldable f,Applicative m) => <br />
(a -> b -> m c) -> t a -> f b -> m (t c)<br />
zipWithTFA g t f = sequenceA (zipWithTF g t f)<br />
</haskell><br />
<br />
The code above fails with a [[pattern match]] error when the <hask>Foldable</hask> container doesn't have enough input. Here is an alternative version which provides friendlier error reports and makes use of <hask>State</hask> instead of the self defined Supply [[monad]].<br />
<br />
<haskell><br />
module GenericZip <br />
(zipWithTF,<br />
zipTF,<br />
zipWithTFA,<br />
zipWithTFM) where<br />
<br />
<br />
import Data.Foldable<br />
import Data.Traversable<br />
import qualified Data.Traversable as T<br />
import Control.Applicative<br />
import Control.Monad.State <br />
<br />
-- | The state contains the list of values obtained form the foldable container<br />
-- and a String indicating the name of the function currectly being executed<br />
data ZipState a = ZipState {fName :: String,<br />
list :: [a]}<br />
<br />
-- | State monad containing ZipState<br />
type ZipM l a = State (ZipState l) a<br />
<br />
-- | pops the first element of the list inside the state<br />
pop :: ZipM l l<br />
pop = do <br />
st <- get <br />
let xs = list st<br />
n = fName st<br />
case xs of<br />
(a:as) -> do put st{list=as}<br />
return a<br />
[] -> error $ n ++ ": insufficient input"<br />
<br />
-- | pop a value form the state and supply it to the second <br />
-- argument of a binary function <br />
supplySecond :: (a -> b -> c) -> a -> ZipM b c<br />
supplySecond f a = do b <- pop <br />
return $ f a b<br />
<br />
zipWithTFError :: (Traversable t,Foldable f) => <br />
String -> (a -> b -> c) -> t a -> f b -> t c <br />
zipWithTFError str g t f = evalState (T.mapM (supplySecond g) t) <br />
(ZipState str (toList f))<br />
<br />
<br />
zipWithTF :: (Traversable t,Foldable f) => (a -> b -> c) -> t a -> f b -> t c<br />
zipWithTF = zipWithTFError "GenericZip.zipWithTF"<br />
<br />
zipTF :: (Traversable t, Foldable f) => t a -> f b -> t (a,b)<br />
zipTF = zipWithTFError "GenericZip.zipTF" (,) <br />
<br />
<br />
zipWithTFM :: (Traversable t,Foldable f,Monad m) => <br />
(a -> b -> m c) -> t a -> f b -> m (t c)<br />
zipWithTFM g t f = T.sequence (zipWithTFError "GenericZip.zipWithTFM" g t f)<br />
<br />
zipWithTFA :: (Traversable t,Foldable f,Applicative m) => <br />
(a -> b -> m c) -> t a -> f b -> m (t c)<br />
zipWithTFA g t f = sequenceA (zipWithTFError "GenericZip.zipWithTFA" g t f)<br />
</haskell><br />
Recent versions of <hask>Data.Traversable</hask> include generalizations of <hask>mapAccumL</hask> and <hask>mapAccumR</hask> from lists to Traversables (encapsulating the state monad used above):<br />
<haskell><br />
mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)<br />
mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)<br />
</haskell><br />
Using these, the first version above can be written as<br />
<haskell><br />
zipWithTF :: (Traversable t, Foldable f) => (a -> b -> c) -> t a -> f b -> t c<br />
zipWithTF g t f = snd (mapAccumL map_one (toList f) t)<br />
where map_one (x:xs) y = (xs, g y x)<br />
</haskell><br />
Replace <hask>mapAccumL</hask> with <hask>mapAccumR</hask> and the elements of the Foldable are zipped in reverse order.<br />
Similarly, we can define a generalization of <hask>reverse</hask> on Traversables, which preserves the shape but reverses the left-to-right position of the elements:<br />
<haskell><br />
reverseT :: (Traversable t) => t a -> t a<br />
reverseT t = snd (mapAccumR (\ (x:xs) _ -> (xs, x)) (toList t) t)<br />
</haskell></div>RichardSmith