https://wiki.haskell.org/api.php?action=feedcontributions&user=Gwern&feedformat=atomHaskellWiki - User contributions [en]2021-07-25T23:15:45ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Infinity_and_efficiency&diff=63961Infinity and efficiency2021-02-06T15:20:20Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Tanimoto</p>
<hr />
<div>[[Category:Idioms]]<br />
<br />
In this article we demonstrate how to check the efficiency of an implementation by checking for proper results for infinite input.<br />
In general, it is harder to reason about time and memory complexity of an implementation than about its correctness.<br />
In fact, in Haskell inefficient implementations sometimes turn out to be wrong implementations.<br />
<br />
A very simple example is the function <code>reverse . reverse</code> which seems to be an inefficient implementation of <code>id</code>.<br />
In a language with [[strict semantics]], these two functions are the same.<br />
But since the [[non-strict semantics]] of Haskell allows infinite data structures, there is a subtle difference,<br />
because for an infinite input list, the function <code>reverse . reverse</code> is undefined, whereas <code>id</code> is defined.<br />
<br />
Now let's consider a more complicated example.<br />
Say we want to program a function that removes elements from the end of a list,<br />
just like <code>dropWhile</code> removes elements from the beginning of a list.<br />
We want to call it <code>dropWhileRev</code>.<br />
(As a more concrete example, imagine a function which removes trailing spaces.)<br />
A simple implementation is<br />
<haskell><br />
dropWhileRev :: (a -> Bool) -> [a] -> [a]<br />
dropWhileRev p = reverse . dropWhile p . reverse<br />
</haskell><br />
You probably have already guessed that it also does not work for infinite input lists.<br />
Incidentally, it is also inefficient, because <code>reverse</code> requires to compute all list nodes<br />
(although it does not require to compute the values stored in the nodes).<br />
Thus the full list skeleton must be held in memory.<br />
However, it is possible to implement <code>dropWhileRev</code> in a way that works for more kinds of inputs.<br />
<haskell><br />
dropWhileRev :: (a -> Bool) -> [a] -> [a]<br />
dropWhileRev p =<br />
foldr (\x xs -> if p x && null xs then [] else x:xs) []<br />
</haskell><br />
Here, <code>foldr</code> formally inspects the list from right to left,<br />
but it actually processes data from left to right.<br />
Whenever a run of elements that matches the condition <code>p</code> occurs, these elements are held until the end of the list is encountered (then they are dropped),<br />
or when a non-matching list element is found (then they are emitted).<br />
The crux is the part <code>null xs</code>, which requires to do recursive calls within <code>foldr</code>.<br />
This works in many cases, but it fails if the number of matching elements becomes too large.<br />
The maximum memory consumption depends on the length of the runs of non-matching elements,<br />
which is much more efficient than the naive implementation above.</div>Gwernhttps://wiki.haskell.org/index.php?title=Abbot&diff=63960Abbot2021-02-06T15:20:15Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Heinlein</p>
<hr />
<div>abbot.galois.com is the current physical machine that hosts several widely used Haskell virtual hosts:<br />
<br />
* cvs.haskell.org<br />
* darcs.haskell.org<br />
* hackage.haskell.org<br />
<br />
This page is intended to be the document that outlines the practices and procedures used to maintain abbot. Additionally, it may contain information about downtimes and upgrades.<br />
<br />
== Platform Notes ==<br />
<br />
abbot is an HP ProLiant DL120 G6 equipped with<br />
<br />
* quad-core 2.40GHz Xeon X3430 processor<br />
* 8 GB RAM<br />
* 680GB RAID-1 filesystem<br />
* Debian lenny amd64<br />
<br />
Most user-maintained directory trees are backed up nightly: /etc, /home, /opt, /srv, /usr/local, and /var.<br />
<br />
Questions or requests for help can be addressed to haskell-infrastructure@community.galois.com.<br />
<br />
== Account Creation ==<br />
<br />
Once someone has been approved for an account, the new user should submit three items:<br />
<br />
# a preferred username<br />
# a valid public SSH key: password logins are discouraged and may be disallowed in the future<br />
# an e-mail address: abbot does not spool mail; outbound mail needs to be rewritten with a valid off-site address<br />
<br />
When those are received, the account can be created:<br />
<br />
# <tt>adduser --disabled-password --gecos "Full Name" newuser</tt><br />
# <tt>chmod -R go-rwx /home/newuser</tt><br />
# Add new user to any necessary supplementary groups: cvs, haskell, hackage, ...<br />
# install public SSH key as <tt>/home/newuser/.ssh/authorized_keys</tt><br />
# add off-site e-mail address to <tt>/etc/aliases</tt> and <tt>/etc/email-addresses</tt><br />
<br />
A user password should only be created when that person needs <tt>sudo</tt> privileges.<br />
<br />
[[User:Heinlein|Heinlein]] 18:03, 6 April 2010 (UTC)</div>Gwernhttps://wiki.haskell.org/index.php?title=UnicodeByteString&diff=63959UnicodeByteString2021-02-06T15:20:14Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by JohanTibell</p>
<hr />
<div>== Motivation ==<br />
<br />
<hask>ByteString</hask> provides a faster and more memory efficient data type than <hask>[Word8]</hask> for processing raw bytes. By creating a Unicode data type similar to <hask>ByteString</hask> that deals in units of characters instead of units of bytes we can achieve similar performance improvements over <hask>String</hask> for text processing. A Unicode data type also removes the error prone process of keeping track of strings encoded as raw bytes stored in <hask>ByteString</hask>s. Using functions such as <hask>length</hask> on a Unicode string just works even though different encodings use different numbers of bytes to represent a character.<br />
<br />
== Specification ==<br />
<br />
A new module, <hask>Text.Unicode</hask>, defines the efficient Unicode string data type:<br />
<br />
<haskell>data UnicodeString</haskell><br />
<br />
Functions to encode and decode Unicode strings to and from <hask>ByteString</hask>s are provided together with <hask>Data.List</hask> like functions.<br />
<br />
<haskell><br />
data Encoding = Ascii | Utf8 | Utf16 | Iso88591<br />
<br />
decode :: Encoding -> ByteString -> UnicodeString<br />
encode :: Encoding -> UnicodeString -> ByteString<br />
</haskell><br />
<br />
=== Error handling ===<br />
<br />
When a <hask>ByteString</hask> is decoded using the wrong codec several error handling strategies are possible:<br />
<br />
* An exception is raised using <hask>error</hask>. This may be fine for many cases.<br />
* Unknown byte sequences are replaced with some character (e.g. <hask>'?'</hask>). This is useful for debugging, etc. where some input/output is better than none.<br />
* The decode function returns values of type <hask>Either CodecError UnicodeString</hask> where <hask>CodecError</hask> contains some useful error information.<br />
<br />
The final API should provide at least a few error handling strategies of different sophistication.<br />
<br />
One example in this design space for error handling is this iconv library:<br />
http://haskell.org/~duncan/iconv/<br />
It provides a most general conversion function with type:<br />
<haskell><br />
:: EncodingName -- ^ Name of input string encoding<br />
-> EncodingName -- ^ Name of output string encoding<br />
-> L.ByteString -- ^ Input text<br />
-> [Span]<br />
<br />
data Span =<br />
-- | An ordinary output span in the target encoding<br />
Span !S.ByteString<br />
-- | An error in the conversion process. If this occurs it will be the<br />
-- last span.<br />
| ConversionError !ConversionError<br />
</haskell><br />
<br />
Then the other simpler error handling strategies are wrappers over this interface. One converts strictly and returns Either L.ByteString ConversionError, the other converts lazily and uses exceptions. There is also a fuzzy mode where conversion errors are ignored or transliterated, using similar replacement characters or <hask>'?'</hask>.<br />
<br />
=== I/O ===<br />
<br />
Several I/O functions that deal with <hask>UnicodeString</hask>s might be needed. All text based I/O should require an explicit encoding or use the default encoding (as set by the user's locale). Example:<br />
<br />
<haskell><br />
readFile :: Encoding -> FilePath -> UnicodeString<br />
</haskell><br />
<br />
== Open Issues ==<br />
<br />
=== API duplication ===<br />
<br />
The <hask>Data.List</hask> API is already duplicated in large parts in <hask>Data.ByteString</hask>. It will be duplicated again here. Will keeping the APIs in sync be a huge pain in the future?<br />
<br />
=== New I/O library ===<br />
<br />
How many new I/O functions are needed? Would it be enough to use <hask>ByteString</hask>'s I/O interface:<br />
<br />
<haskell><br />
import qualified Data.ByteString as B<br />
<br />
echo = do<br />
content <- decode Utf8 <$> B.readFile "myfile.txt"<br />
B.putStrLn $ encode Utf8 content<br />
</haskell><br />
<br />
=== Different representations ===<br />
<br />
Should the encoding used to represent Unicode code points be included in the type?<br />
<br />
<haskell><br />
data Encoding e => UnicodeString e<br />
</haskell><br />
<br />
This might save some recoding as opposed to always using the same internal encoding for <hask>UnicodeString</hask>. It's necessary that UnicodeString can be used between different text processing libraries. Is this possible or will any library end up specifying a particular value for <hask>Encoding e</hask> and thus make it harder to interact with that library?<br />
<br />
This approach is used by <hask>CompactString</hask><br />
<br />
http://twan.home.fmf.nl/compact-string/<br />
<br />
== References ==<br />
<br />
Python 3000 will see an overhaul of their Unicode approach, including a new <code>bytes</code> type, a merge of <code>str</code> and <code>unicode</code> and a new I/O library. This proposals takes many ideas from that overhaul. The relevant PEPs are:<br />
<br />
# http://www.python.org/dev/peps/pep-0358/ - PEP 3116 -- New I/O<br />
# http://python.org/dev/peps/pep-3116/ - PEP 358 -- The "bytes" Object<br />
# http://www.python.org/dev/peps/pep-3137/ - PEP 3137 -- Immutable Bytes and Mutable Buffer</div>Gwernhttps://wiki.haskell.org/index.php?title=Lazy_evaluation&diff=63958Lazy evaluation2021-02-06T15:20:08Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Oldmanmike</p>
<hr />
<div>'''Lazy evaluation''' is a method to evaluate a Haskell program. It means that expressions are not evaluated when they are bound to variables, but their evaluation is '''deferred''' until their results are needed by other computations. In consequence, arguments are not evaluated before they are passed to a function, but only when their values are actually used.<br />
<br />
Technically, lazy evaluation means [http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_name call-by-name] plus [[Sharing]]. A kind of opposite is [[eager evaluation]].<br />
<br />
Lazy evaluation is part of operational semantics, i.e. ''how'' a Haskell program is evaluated. The counterpart in denotational semantics, i.e. ''what'' a Haskell program computes, is called [[Non-strict semantics]]. This semantics allows one to bypass undefined values (e.g. results of infinite loops) and in this way it also allows one to process formally infinite data.<br />
<br />
While lazy evaluation has many advantages, its main drawback is that memory usage becomes hard to predict. The thing is that while two expressions, like <hask>2+2 :: Int</hask> and <hask>4 :: Int</hask>, may denote the same value 4, they may have very different sizes and hence use different amounts of memory.<br />
<br />
An extreme example would be the infinite list<br />
<hask>1 : 1 : 1 …</hask> and the expression <hask> let x = 1:x in x </hask>. The latter is represented as a cyclic graph, and takes only finite memory, but its denotation is the former infinite list.<br />
<br />
== See also ==<br />
<br />
* [[Lazy vs. non-strict]]<br />
* [https://hackhands.com/guide-lazy-evaluation-haskell/ The Incomplete Guide to Lazy Evaluation] – A series of tutorials on lazy evaluation: How it works, how it makes code more modular, how it relates to non-strict semantics, and other things.<br />
* [http://alpmestan.com/posts/2013-10-02-oh-my-laziness.html Oh my laziness!] – An introduction to laziness and strictness in Haskell.<br />
<br />
[[Category:Glossary]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Type&diff=63957Type2021-02-06T15:20:07Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Spookylukey</p>
<hr />
<div>In Haskell, '''types''' are how you describe the data your program will work with.<br />
<br />
[[Category:Language]]<br />
<br />
==Data declarations==<br />
<br />
One introduces, or declares, a type in Haskell via the <code>data</code> statement. In general a data declaration looks like:<br />
<br />
data [context =>] type tv1 ... tvi = con1 c1t1 c1t2... c1tn |<br />
... | conm cmt1 ... cmtq<br />
[deriving]<br />
<br />
which probably explains nothing if you don't already know Haskell!<br />
<br />
The essence of the above statement is that you use the keyword <hask>data</hask>, supply an optional context, give the type name and a variable number of [[type variable]]s. This is then followed by a variable number of [[constructor]]s, each of which has a list of [[type variable]]s or [[type constant]]s. At the end, there is an optional <code>deriving</code>.<br />
<br />
There are a number of other subtleties associated with this, such as requiring parameters to the data constructors to be [[eager]], what [[Type class|class]]es are allowed in the [[deriving]], use of [[field]] names in the constructors<br />
and what the [[context]] actually does. Please refer to the specific articles for more on each of those.<br />
<br />
Let's look at some examples. The Haskell standard data type [[Maybe]] is typically declared as:<br />
<haskell><br />
data Maybe a = Just a | Nothing<br />
</haskell><br />
What this means is that the type '''Maybe''' has one type variable, represented by the ''a'' and two [[constructor]]s '''Just''' and '''Nothing'''. (Note that Haskell requires type names and constructor names to begin with an uppercase letter). The '''Just''' constructor takes one parameter, of type ''a''.<br />
<br />
As another example, consider binary [[Tree]]s. They could be represented by:<br />
<haskell><br />
data Tree a = Branch (Tree a) (Tree a) | Leaf a<br />
</haskell><br />
Here, one of the constructors, '''Branch''' of '''Tree''' takes two trees as<br />
parameters to the constructor, while '''Leaf''' takes a value of type ''a''. This type of recursion is a very common [[:Category:Idioms |pattern]] in Haskell.<br />
<br />
==Type and newtype==<br />
<br />
The other two ways one may introduce types to Haskell programs are via the <hask>type</hask> and <hask>newtype</hask> statements.<br />
<br />
<hask>type</hask> introduces a synonym for a type and uses the same data constructors. <hask>newtype</hask> introduces a renaming of a type and requires you to provide new constructors.<br />
<br />
When using a <hask>type</hask> declaration, the type synonym and its base type are interchangeble almost everywhere (There are some restrictions when dealing with [[instance]] declarations). For example, if you had the declaration:<br />
<br />
<haskell><br />
type Name = String<br />
</haskell><br />
<br />
then any [[function]] you had declared that had <hask>String</hask> in its signature could be used on any element of type <code>Name</code><br />
<br />
However, if one had the declaration:<br />
<br />
<haskell> <br />
newtype FirstName = FirstName String<br />
</haskell><br />
<br />
this would no longer be the case. Functions would have to be declared that actually were defined on '''FirstName'''. Often, one creates a deconstructor at the same time which helps alleviate this requirement. e.g.:<br />
<haskell><br />
unFirstName :: FirstName -> String<br />
unFirstName (FirstName s) = s<br />
</haskell><br />
This is often done by the use of [[field|field labels]] in the <code>newtype</code>. (Note that many consider the Haskell field implementation sub-optimal, while others use it extensively. See [[Programming guidelines#Records|Programming guidelines]] and [[Future of Haskell]])<br />
<br />
==A simple example==<br />
<br />
Suppose you want to create a program to play bridge. You need something to represent cards. Here is one way to do that.<br />
<br />
First, create data types for the suit and card number.<br />
<haskell><br />
data Suit = Club | Diamond | Heart | Spade<br />
deriving (Read, Show, Enum, Eq, Ord)<br />
<br />
data CardValue = Two | Three | Four<br />
| Five | Six | Seven | Eight | Nine | Ten <br />
| Jack | Queen | King | Ace<br />
deriving (Read, Show, Enum, Eq, Ord)<br />
</haskell><br />
Each of these uses a [[deriving]] clause to allow us to convert them from / to [[String]] and Int, test them for equality and ordering. With types like this, where there are no [[type variable]]s, equality is based upon which constructor is used and order is determined by the order you wrote them, e.g. <code>Three</code> is less than <code>Queen</code>.<br />
<br />
Now we define an actual <code>Card</code><br />
<haskell> <br />
data Card = Card {value :: CardValue, <br />
suit :: Suit}<br />
deriving (Read, Show, Eq)<br />
</haskell><br />
In this definition, we use [[field]]s, which give us ready made functions to access the two parts of a <code>Card</code>. Again, [[type variables]] were not used, but the data [[constructor]] requires its two parameters to be of specific types, <code>CardValue</code> and <code>Suit</code>.<br />
<br />
The deriving clause here only specifies three of our desired [[Type class|classes]], we supply [[instance]] declarations for [[Ord]] and [[Enum]]:<br />
<haskell><br />
instance Ord Card where<br />
compare c1 c2 = compare (value c1, suit c1) (value c2, suit c2)<br />
<br />
instance Enum Card where<br />
toEnum n = let (v,s) = n`divMod`4 in Card (toEnum v) (toEnum s)<br />
fromEnum c = fromEnum (value c) * 4 + fromEnum (suit c)<br />
</haskell><br />
Finally, we alias the type <code>Deck</code> to a list of <code>Card</code>s<br />
and populate the deck with a [[list comprehension]] <br />
<haskell><br />
type Deck = [Card]<br />
<br />
deck::Deck<br />
deck = [Card val su | val <- [Two .. Ace], su <- [Club .. Spade]]<br />
</haskell><br />
<br />
==Please add==<br />
<br />
Further illustrative examples would be most appreciated.<br />
<br />
==See also==<br />
Read the articles about data [[constructor]]s and [[Type class|class]]es. As well the [http://haskell.org/definition/haskell98-report.pdf Haskell 98 report] and your chosen implementation (e.g. [[GHC/Documentation]]) have the latest words.<br />
<br />
*[[Determining the type of an expression]] - Let the Haskell compiler compute the type of expression<br />
*[[:Category:Language extensions | Language extensions]] - many language extensions are to do with changes to the type system.<br />
*[[Smart constructors]] shows some interesting examples including a non-trivial usage of <code>newtype</code>.<br />
*[[Unboxed type]] shows ways to have values closer to the bare metal :).<br />
*[[Phantom type]] discusses types without constructors.<br />
*[[Type witness]] gives an example of [[Generalised algebraic datatype | GADTs]], a [[GHC]] extension.<br />
*[[Existential type]] shows how to implement a common O-O programming paradigm.<br />
*[[Type arithmetic]] implements the [[Peano numbers]].<br />
*[[Reified type]], [[Non-trivial type synonyms]], [[Abstract data type]], [[Concrete data type]], [[Algebraic data type]].<br />
*[[Research_papers/Type_systems]] allow the curious to delve deeper.<br />
<br />
Languages: [[型|ja]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Darcs&diff=63956Darcs2021-02-06T15:20:06Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Ppelleti</p>
<hr />
<div>'''darcs''' is a peer-to-peer revision control system, written in Haskell. It is the standard RCS of the Haskell community.<br />
<br />
== Understanding darcs ==<br />
<br />
You can think of a darcs repository as containing these things:<br />
<br />
* '''Patches''': a patch is a collection of changes that forms the unit of synchronisation with other repositories<br />
* Unrecorded '''changes''' to known files and directories<br />
* '''Unmanaged items''' (files and directories)<br />
* '''Boring items''': anything with a name matched in <tt>_darcs/prefs/boring</tt><br />
* The '''unrevert cache''' of changes<br />
<br />
Note that some projects are keen on making sure all derivative items are "boring" rather than merely unknown items that will show up with <tt>darcs wh -l</tt>. Other projects less so.<br />
<br />
== Operations ==<br />
<br />
=== Unmanaged items ===<br />
<br />
*<tt>darcs whatsnew -l</tt>: show changes to managed files, and unmanaged items<br />
<br />
*'''creating a item''': add item to the unmanaged items.<br />
<br />
*<tt>darcs add</tt>: convert the unmanaged item into a change to create the item and its contents<br />
<br />
*<tt>darcs remove</tt>: add a change which empties the item and deletes it, but keep it as an unmanaged item.<br />
<br />
=== Changes ===<br />
<br />
*<tt>darcs whatsnew</tt>: show unrecorded changes<br />
<br />
*'''removing a managed item''': add a change to remove the item<br />
<br />
*'''editing a managed file''': add a change for the edit<br />
<br />
*<tt>darcs mv</tt>: add a change to move an item<br />
<br />
*<tt>darcs replace</tt>: add a change to replace text in a file<br />
<br />
*<tt>darcs record</tt>: record changes to add a patch<br />
<br />
*<tt>darcs unrecord</tt>: remove a patch by turning back it into unrecorded changes<br />
<br />
*<tt>darcs amend-record</tt>: replace a patch with one with added changes<br />
<br />
*<tt>darcs revert</tt>: remove changes and put them in the unrevert cache. ''Warning: you will lose the previous contents of the unrevert cache.''<br />
<br />
*<tt>darcs unrevert</tt>: take changes out of the unrevert cache and add them to the unrecorded changes.<br />
<br />
=== Patches ===<br />
<br />
*<tt>darcs changes</tt>: show patches<br />
<br />
*<tt>darcs send --output=''FILE''</tt>: make an email bundle from patches<br />
<br />
*<tt>darcs send --to=''ADDRESS''</tt>: send an email bundle from patches<br />
<br />
*<tt>darcs pull</tt>: add patches from another repository<br />
<br />
*<tt>darcs push</tt>: add patches from this repository to another repository<br />
<br />
*<tt>darcs apply</tt>: add patches from an email bundle<br />
<br />
*<tt>darcs rollback</tt>: add a patch that is the inverse of an existing patch<br />
<br />
*<tt>darcs obliterate</tt>: remove a patch. ''Warning: if the patch doesn't exist elsewhere, you will lose that work.''<br />
<br />
*<tt>darcs tag</tt>: add a tag for the current set of patches<br />
<br />
=== Repositories ===<br />
<br />
*<tt>darcs initialize</tt>: create a new empty repository<br />
<br />
*<tt>darcs get</tt>: create a new empty repository and add patches from another repository<br />
<br />
== External links ==<br />
<br />
* [http://darcs.net/ darcs]<br />
* [http://hub.darcs.net darcsden/darcs hub] free darcs repository hosting<br />
* [http://en.wikibooks.org/wiki/Understanding_darcs Understanding darcs] - an illustrated wikibook about darcs and patch theory<br />
* [http://blog.interlinked.org/tutorials/darcs.html Darcs, Taking version control to the next level], a tutorial<br />
* [http://mark.stosberg.com/blog/2005/01/benefits-from-a-real-world-switch-from-cvs-to-darcs.html Benefits from a real world switch from CVS to darcs]<br />
* Implementation details of <code>darcs</code> show motivating examples for [[generalised algebraic datatype]]s. The motivations are described in David Roundy's slides [http://darcs.net/fosdem_talk/talk.pdf Implementing the darcs patch formalism and verifying it] (see p. 11, 13--14.). The talk mentions also the notions of [[phantom type]], and [[existential type]], and [[type witness]] (see p. 15).<br />
* See [http://web.archive.org/web/20070409170354/http://darcs.net/DarcsWiki/Talks also other talks] on <code>darcs</code>. One of them ([cufp.galois.com/2005/slides/DavidRoundy.pdf The Myth and Reality of using Haskell in the ‘Real World’]) discusses a more general topic: usefulness of Haskell (in real life) and in general, the power of (lazy) functional programming.<br />
* [http://wiki.darcs.net/ConfictMiseryAnalysis Conflict bug] -(a problem in Darcs-1)<br />
* <s>Another free darcs hosting (for open source projects) at patch-tag.com</s><br />
<br />
[[Category:Tools]]</div>Gwernhttps://wiki.haskell.org/index.php?title=XML_Light&diff=63955XML Light2021-02-06T15:20:05Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by DonStewart</p>
<hr />
<div>== XML Light ==<br />
<br />
This page collections documentation and examples about the library<br />
[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/xml xml], a lightweight xml parser and pretty printer for Haskell,<br />
developed at Galois, Inc.<br />
<br />
== Features ==</div>Gwernhttps://wiki.haskell.org/index.php?title=ZipFold&diff=63953ZipFold2021-02-06T15:20:04Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Conal</p>
<hr />
<div>[[Category:Packages]]<br />
<br />
== Abstract ==<br />
<br />
'''ZipFold''' is a small package zipping folds, as described in a [http://conal.net/blog/tag/zip collection of blog posts] and inspired by the post [http://squing.blogspot.com/2008/11/beautiful-folding.html "Beautiful Folding"] by Max Rabkin.<br />
<br />
Besides this wiki page, here are more ways to find out about ZipFold:<br />
* Visit the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ZipFold Hackage page] for library documentation and to download & install.<br />
* Or install with <tt>cabal install ZipFold</tt>.<br />
* Get the code repository: <tt>darcs get http://conal.net/repos/ZipFold</tt>.<br />
<!-- * See the [[ZipFold/Versions| version history]]. --></div>Gwernhttps://wiki.haskell.org/index.php?title=Zsh&diff=63954Zsh2021-02-06T15:20:04Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by GerardMilmeister</p>
<hr />
<div>==Z Shell Completion for GHC, Cabal and Hugs==<br />
<br />
The Z Shell is a powerful shell with extensive completion support.<br />
<br />
==Features==<br />
<br />
The <tt>_ghc</tt> script supports completion for <tt>ghc</tt> and<br />
<tt>ghc-pkg</tt>. The completion features include the following:<br />
<br />
* all options with a description for each option<br />
* directories<br />
* package names<br />
* system libraries (<tt>-l</tt> option)<br />
* <tt>ghc-pkg</tt> commands<br />
<br />
The <tt>_cabal</tt> script support completion for the <tt>cabal</tt><br />
command. The completion features include the following:<br />
<br />
* Cabal commands<br />
* all options with a description for each option<br />
* directories<br />
* package names<br />
<br />
The <tt>_hugs</tt> script provides completion for options.<br />
<br />
==Installation==<br />
<br />
Put the <tt>_ghc</tt>, <tt>_cabal</tt> and <tt>_hugs</tt> scripts in a path<br />
that <tt>zsh</tt> searches during autoloading, for example<br />
<tt>/usr/share/zsh/functions</tt> or a private directory (which<br />
must be added to the <tt>FPATH</tt> environment variable).<br />
<br />
Completion must be enabled by adding to <tt>.zshrc</tt> the<br />
following lines:<br />
<br />
autoload -U compinit<br />
compinit<br />
<br />
Completion functionality can be configured using styles.<br />
These are set with the <tt>zstyle</tt> function.<br />
<br />
Here are some examples:<br />
<br />
zstyle ':completion:*' completer _complete _match _approximate<br />
zstyle ':completion:*' use-cache on<br />
zstyle ':completion:*:approximate:*' max-errors 1 numeric<br />
<br />
See the <tt>zsh</tt> documenation for details on configuring the<br />
completion system.<br />
<br />
==Download==<br />
<br />
[http://gemi.fedorapeople.org/haskell/_ghc _ghc]<br />
[http://gemi.fedorapeople.org/haskell/_hugs _hugs]<br />
[http://gemi.fedorapeople.org/haskell/_cabal _cabal]<br />
<br />
[[Category:Tools]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Bot/Versions&diff=63952Bot/Versions2021-02-06T15:20:03Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Conal</p>
<hr />
<div>== Version 0 ==<br />
<br />
=== Version 0.1 ===<br />
<br />
* Updated according to blog post [http://conal.net/blog/posts/applicative-bots Applicative bots].<br />
<br />
=== Version 0.0 ===<br />
<br />
* New project. See [http://conal.net/blog/tag/bot/ some related blog posts].</div>Gwernhttps://wiki.haskell.org/index.php?title=UTF-8&diff=63951UTF-82021-02-06T15:20:02Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by PhilipNeustrom</p>
<hr />
<div>[[Category:Code]]<br />
<br />
The simplest solution seems to be to use the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/utf8-string utf8-string package] from Galois. It <br />
provides a drop-in replacement for System.IO<br />
<br />
''What about other string encodings?''<br />
<br />
== Example ==<br />
If we use a function from System.IO.UTF8, we should also hide the equivalent one from the Prelude. (Alternatively, we could import the UTF8 module qualified)<br />
<br />
<haskell><br />
> import System.IO.UTF8<br />
> import Prelude hiding (readFile, writeFile)<br />
> import System.Environment (getArgs)<br />
</haskell><br />
<br />
The readFile and writeFile functions are the same as before...<br />
<br />
<haskell><br />
> main :: IO ()<br />
> main =<br />
> do args <- getArgs<br />
> mapM_ reverseUTF8File args<br />
<br />
> reverseUTF8File :: FilePath -> IO ()<br />
> reverseUTF8File f =<br />
> do c <- readFile f<br />
> writeFile (f ++ ".rev") $ reverseLines c<br />
> where<br />
> reverseLines = unlines . map reverse . lines<br />
</haskell></div>Gwernhttps://wiki.haskell.org/index.php?title=Toolmaking_libraries&diff=63950Toolmaking libraries2021-02-06T15:20:00Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by PhilippaCowderoy</p>
<hr />
<div>== Basic concept ==<br />
<br />
Writing tools involves duplicating work that gets done over and over, and which is affected by the existence of extensions. So let's define interfaces for libraries that make this easier and build some initial implementations, while letting new Haskell implementations with new extensions provide their own implementations that hopefully make the extensions less painful to deal with.<br />
== Views ==<br />
<br />
Different tools need different information about code - for example, haddock doesn't care about terms at all, whereas other tools might want to know about dependencies and yet others might perform abstract interpretations on code. So we should provide different views of a source file, with different modules implementing them.<br />
<br />
# Apps like Haddock need to see the [[#Bindings only|bindings]] present in a module and some information about those bindings, but no terms. Some term-relevant analyses could still be usefully provided - so long as they're done on-demand, apps that don't need them won't be restricted by tighter well-formedness constraints.<br />
# Other applications could use a desugared 'core' language (and preferably means to find the corresponding source for a given piece of core code). At least two variants would make sense:<br />
#* An untyped [[#Core languages|core]]. Producing such a language isn't too hard, though there are arguments to be had as to how to handle type classes.<br />
#* An explicitly typed [[#Core languages|core]]. This could be trickier - the Right Thing would appear to be a core sufficiently expressive to handle type-preserving translations from the numerous extensions kicking around. Type classes are again an issue, in that much of the work involved with them is in resolving which instance to use - this can be dealt with, but requires some thought.<br />
=== Proposed interfaces ===<br />
==== Bindings only ====<br />
<br />
A sketch proposal for a "just the names" interface (... where I've not filled in concrete details yet, feel free to add in the obvious):<br />
<br />
<haskell><br />
-- [Item] corresponds to the order the items appear in the source<br />
data Module = Module Identifier [Export] [Item]<br />
data Export = ...<br />
data Item = Comment String |<br />
Function FuncDec |<br />
Fixity FixityDec |<br />
Type TypeDec |<br />
Class ClassDec |<br />
Instance InstanceDec |<br />
Import ImportDec |<br />
... -- new extensions may add new constructors, tools should handle these gracefully<br />
<br />
data FuncDec = FuncDec Identifier (Maybe Type)<br />
data FixityDec = FixDec Fixity Int <br />
data Fixity = FLeft | FRight | FNon<br />
data TypeDec = TypeDec {name :: Identifier,<br />
parms,<br />
constructors :: [DataConDec],<br />
...} |<br />
TypeSynonym ... |<br />
NewType ...<br />
data ClassDec = ... -- keep abstract<br />
data InstanceDec = ... -- keep abstract<br />
data ImportDec = ...<br />
<br />
data Type = ... -- keep abstract<br />
<br />
-- parse source<br />
readSource :: String -> Module<br />
<br />
{- queries on Module -}<br />
funcs :: Module -> [FuncDec]<br />
types :: Module -> [TypeDec]<br />
classes :: Module -> [ClassDec]<br />
instances :: Module -> [InstanceDec]<br />
<br />
{- compatibility - extended/custom version of lib will want additional such queries -}<br />
class MaybeH98 dec where<br />
isH98 :: dec -> Bool<br />
<br />
-- instances of MaybeH98 for all Dec structures<br />
<br />
{- queries on InstanceDec -}<br />
-- print out the 'head' of the instance, "instance <class> <parms>"<br />
showInstanceHead :: InstanceDec -> String<br />
showInstance :: InstanceDec -> String -- use for Show instance<br />
<br />
{- queries on FuncDec -}<br />
-- clearly I have done some handwaving, as FuncDecs'd need tying to their source for this<br />
inferType :: FuncDec -> Type<br />
<br />
{- queries on Type -}<br />
showType :: Type -> String -- use for Show instance, should be legit Haskell code<br />
<br />
-- Any other useful queries want adding?<br />
</haskell><br />
==== Core languages ====<br />
<br />
How about building our untyped core around this language, after going over it with a comb to check it's adequately expressive?:<br />
<br />
<haskell><br />
type Program = [Dec]<br />
<br />
data Dec = Dec Identifier Term<br />
<br />
data Term = Var Identifier |<br />
App Term [Term] |<br />
Lam [Identifier] Term |<br />
Let [Dec] Term | -- recursive let<br />
Case Term [Alt] -- simple case<br />
<br />
data Alt = Alt {constructor :: Identifier, <br />
bindings :: [Identifier],<br />
result :: Term}<br />
</haskell><br />
<br />
Important design choices to note: this isn't a supercombinator language or a variant of ANF, it's an ordinary untyped lambda calculus with minimal extensions to capture pattern matching and binding structure. Including lambda lifting and A-normalisation functions in the library would probably be a good idea. An interpreter may not go amiss either.<br />
<br />
A sensible typed core might use explicit instance lambdas and applications as well as type lambdas and applications in the vein of System F. This would leave resolving which instance to supply to the type inference process. It would need to leave extension mechanisms for new constructs in order to naturally accomodate changes such as GADTs - System Fc is preferable to hacking in casts where it can be used. The library would definitely have to include a typechecker.</div>Gwernhttps://wiki.haskell.org/index.php?title=WikipediaArticleDesign&diff=63949WikipediaArticleDesign2021-02-06T15:19:57Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Tom</p>
<hr />
<div>== Motiviation ==<br />
<br />
The [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Haskell Wikipedia Article] is an ad hoc collection of edits with no overriding structure or theme. The Haskell community should be able to contribute a better article to represent this project. <br />
<br />
Here's a draft structure based on the "[[History_of_Haskell|History of Haskell]]" paper.<br />
<br />
Please make comments on the [[Talk:WikipediaArticleDesign|Discussion page]]<br />
<br />
== Structures ==<br />
<br />
1. History <br />
1.1 Related Languages<br />
<br />
2. Overview and Design Principles<br />
2.1 Laziness<br />
2.2 Purity<br />
2.3 Type classes<br />
2.4 Open and free<br />
<br />
3. Features<br />
3.1 Syntax<br />
3.1.1 Layout<br />
3.1.2 Functions, currying, application, abstraction<br />
3.1.3 Operators<br />
3.1.4 Namespaces<br />
3.1.5 Declarations vs Expressions<br />
3.1.6 List comprehensions<br />
<br />
3.2 Algebraic Data Types<br />
3.2.1 Pattern Matching<br />
3.2.2 Abstract Types<br />
3.2.3 Lists<br />
3.2.4 Tuples<br />
3.2.5 Records<br />
<br />
3.3 Type System<br />
3.3.1 Type classes<br />
3.3.2 Type defaulting<br />
3.3.3 Overloaded Literals<br />
3.3.4 Higher Kinded Polymorphism<br />
3.3.5 Multi-Parameter Type Classes<br />
3.3.6 Functional Dependencies<br />
3.3.7 Type System Extensions<br />
Existential types<br />
Extensible records<br />
Polymorphic Recursion<br />
Higher-Rank Types<br />
Generalized ADTs<br />
Type Families<br />
Unlifted types<br />
Generics<br />
Template Metaprogramming<br />
<br />
3.4 Monads<br />
Overview<br />
Applications <br />
* Monadic IO<br />
* do-notation<br />
* References<br />
* Exceptions<br />
* ST monad<br />
* STM monad<br />
Applicative Functors<br />
Arrows<br />
<br />
3.6 Concurrency and Parallelism<br />
Threads<br />
Shared memory communcation<br />
Futures and sparks<br />
Software Transactional Memory<br />
Data Parallelism<br />
<br />
3.7 Programming in the Large<br />
3.7.1 FFI<br />
3.7.2 Modules<br />
3.7.3 Packages<br />
<br />
3.8 Semantics<br />
* Static semantics<br />
* Dynamic semantics<br />
<br />
3.9 Extensions to Haskell<br />
<br />
4. Implementations<br />
4.1 GHC, GHCi<br />
4.2 Hugs<br />
4.3 NHC, YHC<br />
4.4 Other implementations<br />
<br />
5. Tools<br />
5.0 Profiling<br />
5.1 Debugging<br />
5.2 Testing<br />
5.3 Alex and Happy<br />
5.5 Haddock<br />
5.6 Hoogle and Hayoo <br />
<br />
6. Distribution<br />
* Cabal<br />
* Hackage<br />
* cabal-install<br />
* Haskell Platform<br />
<br />
7. Libraries ''(top 2 libraries by Hackage downloads or notability)''<br />
* Audio<br />
* Codecs<br />
* Concurrency<br />
* Data Structures<br />
* Database<br />
* HDBC<br />
* Games<br />
* 2D<br />
* 3D<br />
* GUIs<br />
* gtk2hs<br />
* wxHaskell<br />
* FRP guis<br />
* Languages<br />
* Math<br />
* Numeric Prelude<br />
* Music<br />
* Haskore<br />
* Network<br />
* System<br />
* Testing<br />
* QuickCheck<br />
* HUnit<br />
* Text<br />
* Unicode/UTF8<br />
* Web<br />
* Happstack<br />
<br />
6. Applications<br />
''Notable open source applications (by popularity)''<br />
<br />
* darcs<br />
* xmonad<br />
* pugs<br />
* pandoc<br />
* gitit<br />
* cpphs<br />
* agda<br />
* yi, leskah<br />
<br />
''Notable commercial applications (citing CUFP)'' <br />
<br />
* Bluespec (Bluespec)<br />
* Cryptol (Galois)<br />
* Atom (Eaton)<br />
* Paradise (credit Suisse)<br />
<br />
''Notable applied research projects (by citations? [http://haskell.org/haskellwiki/Research_papers see here])''<br />
<br />
* Parser combinators<br />
* [Hardware design]<br />
* [http://haskell.org/haskellwiki/Libraries_and_tools/Operating_system Operating systems]<br />
* [http://haskell.org/haskellwiki/Research_papers/Functional_reactive_programming Functional Reactive Programming]<br />
<br />
7. Community<br />
<br />
9 Further Reading</div>Gwernhttps://wiki.haskell.org/index.php?title=Hackage_wiki_page_per_project_discussion&diff=63948Hackage wiki page per project discussion2021-02-06T15:19:56Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Basvandijk</p>
<hr />
<div>== Purpose of this page ? ==<br />
collect thoughts about whether we should provide a wiki page (and maybe even more advanced features such as bug trackers) for all projects hosted on hackage<br />
<br />
I'll post a link to this page to haskell-cafe so everyone should participate<br />
<br />
== Why a Wiki ==<br />
We do have about 2000 packages on hackage. Hackage was made life easier.<br />
While packaging some packages for nix (using [[Hack-Nix]]) I had to write some patches.<br />
<br />
If you have a patch what to do?<br />
Duncan Coutts proposed contacting the maintainer. If you don't receive replies within a time frame write to the haskell-cafe mailinglist. If you can't find him become the new maintainer.<br />
<br />
While contacting the maintainer works very well within 3 days in most cases there are situations where maintainers can't reply because they are on holiday or got very busy.. In these cases I'd like to put my patch somewhere so that others can find them.<br />
<br />
== What could a wiki page be used for? ==<br />
<br />
<br />
a) patches (which are removed when maintainers integrate them upstream)<br />
<br />
b) Howtos and pitfalls (written by users or maintainers)<br />
<br />
c) references to similar projects pointing out differences.<br />
<br />
d) a smart lazy changelog. If a user hits a change he can add this to the<br />
wiki so that others can find out faster which version constraints to<br />
add to their .cabal file.<br />
<br />
This looks like this:<br />
2.20: renamed foo to bar.<br />
<br />
2.48: type change of iwillneverChange :: Int to Maybe Int<br />
<br />
e) a list of changes which will go into the next release of a package.<br />
This may help you figuring out whether you should download the darcs repository.<br />
<br />
f) many other ideas I can't think about yet.<br />
<br />
...<br />
<br />
<br />
== implementation details: ==<br />
<br />
design could look like this:<br />
http://mawercer.de/~marc/hackage-link-example.jpg<br />
<br />
The link would point to the haskell wiki having the url suffix /project-name.<br />
<br />
== When a wiki page can replace a .cabal file update ==<br />
<br />
* naturally it takes some time until most recent cabal updates are used by mainstream.. Eg there is a way to add repository locations now.. But have a look at [http://hackage.haskell.org/packages/archive/happy/1.18.4/happy.cabal happy.cabal] and smile :) Btw: I adopted this usage of the source-repository field for one project.<br />
<br />
* minor dependency changes<br />
<br />
* tell users about experimental branches<br />
<br />
* it's easier to provide important information such as:<br />
<br />
"This package is superseded by XY because: ..."<br />
<br />
** We already have a mechanism to deprecate packages or to mark them as superseded. --[[User:DuncanCoutts|DuncanCoutts]] 00:25, 12 December 2009 (UTC)<br />
<br />
[[User:MarcWeber|Marc Weber]]: Can you explain how this works or point me to the documentation?<br />
<br />
The main point about this wiki idea is that you can attach arbitrary information and you don't have to wait for anyone to do so.<br />
Get things done. Provide patches. Link them on the wiki.<br />
Come back later and discuss your proposals with the maintainer.<br />
Keep summaries of discussions on subjects accessible by everyone.<br />
...<br />
<br />
Of course I know that the maintainers are the people doing the real work.<br />
But look at it from a different view: Having such a forum for all projects by default also means that a maintainer can let others do some of the work knowing that they don't have to reply within some days.<br />
<br />
The wiki can host all information which may be useful but which wasn't foreseen by hackage or cabal devs. We must keep agile and move forward only.<br />
<br />
== Concerns ==<br />
<br />
My (DuncanCoutts) concern is about the consent from package authors. Hackage is a social bargain. We ask package authors to distribute their work through hackage because it provides benefits to the community. If we impose too much on package authors then they may decide it's just not worth it.<br />
<br />
In particular, if we automatically create a wiki page for every package then we are imposing additional obligations on package authors. As a package author I might be concerned that this wiki page duplicates an existing home page or bug tracking system. If there's a wiki page about my project then I am effectively obligated to check it from time to time, since users will inevitably report bugs etc there. It is that extra obligation that package authors may resent.<br />
<br />
There is no problem with such a feature being opt-in, but whether it is something we require and impose on package authors needs much more of a social consensus before we go ahead.<br />
<br />
Reply [[User:MarcWeber|Marc Weber]]: Everybody knows that it is wiki content and will take care.<br />
<br />
About effort: Note that package authors can watch their wiki pages easily.<br />
Authors and maintainers already do the hard work. Watching a wiki page is not mach work compared to writing a library. But they may find wiki contents of foreign projects that useful that they provide some contents their selves<br />
<br />
The above concerns amount to saying that there is (or may be) no value added for the user but nevertheless makes extra work for the maintainer. My (Daniel Wagner) concern is that there may actually be value ''removed'' for the user. A bad, incomplete, or non-existent wiki page can be worse than no page at all, because new users may view the wiki page as the canonical resource. This is especially so because many of the smaller projects have minimal or non-existent homepages (often just the root of a darcs repository) and minimal or non-existent documentation; this puts users in the habit of searching elsewhere for information about using the package. Maintainers that do end up putting effort into their project's pages and documentation will suffer as a result, especially if the projects are too small to garner many wiki-editing users. In this case, an unhelpful wiki page may scare away potential users, despite the existence of other useful resources.<br />
<br />
== concern "The wiki will be outdated" ==<br />
True. Every user must know that wikis naturally are out of date :)<br />
But the question is: Can one wiki page (containing an example)<br />
generate more value than some outdated pages cause damage to you?<br />
<br />
It's hard to say because haskellwiki wiki pages can be found when searching from the start page as well.<br />
<br />
Maybe we can ask users to add the package version so that users will see themselves that content is outdated?<br />
<br />
<br />
Don't think about other people. Think about yourself: Do you mind reading some outdated wiki pages? Do you appreciate the valuable contents which will be exist as well? If you don't mind reading some outdated pages and if you'd like to see more examples about how to use packages you basically support this idea!<br />
Let's not forget that haskell.org is a wiki itself. And naturally parts are outdated as well. You still don't want to miss it, do you?<br />
<br />
== wiki alternatives ==<br />
If content isn't put on a wiki what do people do instead?<br />
* They may do nothing (bad)<br />
* They may write a blog (bad because others don't find it or because content gets out of date). Which way is more likely providing you with valuable information: A blog found by google or an attached wiki page people can keep up to date?<br />
* They may write to the mailinglist. Things are archived forever. On the wiki they are as well but not only a small amount of visitors ever looks at the history of a page..<br />
<br />
== my project already has a wiki ..==<br />
Fine. In this case the haskellwiki wiki page will only have one link telling the user about your page.<br />
<br />
== progress and feedback ==<br />
I've send a short mail to about 100 maintainers to get to know what they think about this idea.<br />
<br />
Consider adding your name only for spam reasons (but send your emal address to marco-oweber@gmx.de so that I can associate them with packages on hackage to got to know who didn't reply)<br />
<br />
I support this idea:<br />
* marco-oweber@gmx.de (Marc Weber)<br />
* clawsie@fastmail.fm (Brad Clawsie)<br />
* newanon@yandex.ru (Oleg Ivanov)<br />
<br />
I support but want opt-out:<br />
* f.nfgnava@tznvy.pbz/rot13 (Sergey Astanin) I think default project wiki is a good thing for users, especially given that many projects don't have links neither to the web page nor to the bug tracker, some are unmaintained public domain, and some don't have even e-mail of the maintainer. However, I think that this wiki policy should be applied only to such “orphaned” projects without evident maintainer/infrastructure. When there is a valid link to project page, bug tracker or stand alone wiki, it's better to direct users there.<br />
<br />
I support but I want opt-in:<br />
* daniel@wagner-home.com (Daniel Wagner) I believe opt-in is the Right Thing, so would vote here even if I didn't have the misgivings I mention above<br />
* daniel.schoepe@googlemail.com (Daniel Schoepe) In general I think it's a very good idea, but imposing it on every package author might discourage some, especially people new to Hackage.<br />
* the idea makes me nervous, but I can live with opt-in (Eric Kow)<br />
* vandijk.roel@gmail.com (Roel van Dijk) I wouldn't mind it as long as it is completely optional. But it is already supported just by setting your homepage to a haskell.org wiki page. And you can always ask a maintainer if he/she can create a wiki for a project or if it's ok if you create a wiki for their project.<br />
<br />
I don't like the idea even if there was a warning such as "This content is contributed by maintainers and users and may be out of date.":<br />
<br />
If you vote here, make sure you've read "wiki alternatives". You can clean up the wiki page. You can't clean up foreign blogs.<br />
* EvanMartin (exactly what Duncan wrote -- I don't have time to vet a third-party page and keep it up to date; I have seen obsolete wikis for too many projects in my time. If I want to use a wiki I could just set it as the home page for my project. Consider adding a "wiki" link to the package description format.)<br />
<br />
I don't care:<br />
*<br />
<br />
I won't tell you:<br />
*<br />
<br />
== users view (beginners) ==<br />
Daniel Wagner told me that the thinks beginners will suffor most.<br />
So I'll start a thread on beginners@haskell.org and ask them :-)<br />
<br />
I'm a beginner, I don't mind reading outdated content. When I see a code snippet I'm going to copy paste it int ghci. If it doesn't work may be challenged and may fix it. Of course I'll contribute by solution and put it on the wiki. I think that such a scratch pad is a nice idea in general.<br />
* put your name here<br />
<br />
I'm a beginner and I fear reading about outdated content. This means that you fear the damage reading outdated content is bigger than the gains you have by reading up to date contents.<br />
* put your name here<br />
<br />
== mailinglist threads ==<br />
* [http://news.gmane.org/gmane.comp.lang.haskell.cafe haskell-cafe]<br />
<br />
* [http://thread.gmane.org/gmane.comp.lang.haskell.beginners/2942 beginners@haskell.org]<br />
<br />
<br />
== Notes ==<br />
You can watch this page</div>Gwernhttps://wiki.haskell.org/index.php?title=Haskell_Platform/FAQ&diff=63947Haskell Platform/FAQ2021-02-06T15:19:55Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by AlistairBayley</p>
<hr />
<div>'''FAQ for the Haskell Platform Projects'''<br />
<br />
;Is the platform portable to Windows?<br />
:Yes. Being able to work on windows is a hurdle for inclusion.<br />
<br />
;What does the platform depend on?<br />
:GHC and the core libraries. <br />
<br />
;What is in the first release?<br />
:The first release will be just extralibs, taken from GHC, with additional tools required to boostrap cabal-install.<br />
<br />
;Who decides what is in, and what is out?<br />
:There will be a formal process for library and tool inclusion or exclusion, based on quanititative metrics for quality and comprehensiveness of the code. Proposals for additions to the platform will have to satisfy these constraints. ''Inclusion is not a personal decision by the core team'', who act only as infrastructure coders.<br />
<br />
;Will the Haskell platform provide a glue layer for API standardisation?<br />
:Unlike the OCaml Batteries proposal, there will be no new glue layer to combine libraries, instead, we rely on the large base library to provide the standard interface types. Addition to the platform is a social process. This social process acts as a checkpoint that ensures base library conformance for candidate libraries seeking admittance. If a candidate library reinvents, for example, a time format, or an exception handling mechanism, the platform process enforces standardisation on the candidate's base API before admission completes. <br />
<br />
[[Category:Community]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Haskell_Platform/Batteries_Included&diff=63946Haskell Platform/Batteries Included2021-02-06T15:19:54Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by DuncanCoutts</p>
<hr />
<div>==Haskell Platform Coverage==<br />
<br />
===Candidates for the initial version===<br />
<br />
* array<br />
* base<br />
* bytestring<br />
* Cabal<br />
* containers<br />
* directory<br />
* editline<br />
* filepath<br />
* haskell98<br />
* hpc<br />
* integer-gmp<br />
* old-locale -- should be deprecated but no replacement yet<br />
* old-time -- deprecated but still very widely used<br />
* packedstring -- deprecated but used by template-haskell<br />
* pretty<br />
* process<br />
* random<br />
* template-haskell<br />
* unix OR Win32 <br />
<br />
* ALUT<br />
* GLUT<br />
* HUnit<br />
* OpenAL<br />
* OpenGL<br />
* QuickCheck<br />
* cgi<br />
* fgl<br />
* haskell-src<br />
* html<br />
* mtl<br />
* network<br />
* parsec<br />
* parallel<br />
* regex-base<br />
* regex-compat<br />
* regex-posix<br />
* stm<br />
* time<br />
* xhtml<br />
<br />
* zlib<br />
* HTTP<br />
* cabal-install<br />
<br />
===Potential candidates for eventual inclusion===<br />
<br />
* Codecs<br />
**base64<br />
**bzlib<br />
**zlib<br />
**dataenc<br />
**encoding<br />
**iconv<br />
**mime<br />
**utf8-string<br />
**tar<br />
**nano-md5/hmac<br />
**pureMD5<br />
<br />
* Control<br />
**arrows<br />
**category-extras<br />
**logict<br />
**maybet<br />
**mtl<br />
**reactive<br />
**monad-lib<br />
<br />
* Data<br />
**array<br />
**binary<br />
**binary-strict<br />
**bloomfilter<br />
**bytestring<br />
**carray<br />
**containers<br />
**dlist<br />
**lazyarray<br />
**numbers<br />
**ranged-sets<br />
**stream<br />
**strict<br />
**suffixtree<br />
**avltree<br />
**bitset<br />
**bktrees<br />
**fingertree<br />
**random-access-list<br />
**heap<br />
<br />
* Database<br />
**hdbc<br />
**takusen<br />
**sqlite<br />
<br />
* Development<br />
**alex<br />
**c2hs<br />
**cpphs<br />
**derive<br />
**haddock<br />
**happy<br />
**cabal<br />
**cabal-install<br />
**hscolour<br />
<br />
* Graphics<br />
** Chart<br />
** gd<br />
** hgl<br />
** hpdf<br />
** opengl<br />
** x11<br />
<br />
* GUI<br />
** gtk2hs<br />
** wxHaskell<br />
<br />
* Languages and parsing<br />
**haskell-src<br />
**Language.C<br />
**parsec<br />
**polyparse<br />
**csv<br />
**feed<br />
**rss<br />
**haxml<br />
**hxt<br />
**xml<br />
**html<br />
**xhtml<br />
**i18n<br />
**hssyck<br />
**pcre-light<br />
**regex<br />
**hstemplate<br />
<br />
* Math<br />
**blas<br />
**hmatrix<br />
**cmath<br />
**fft<br />
**mersenne-random<br />
<br />
* Network<br />
**cgi<br />
**cgi-undecidable<br />
**curl<br />
**download-curl<br />
**fastcgi<br />
**ftphs<br />
**hS3<br />
**http<br />
**network<br />
**network-bytestring<br />
<br />
* Sound<br />
**alut<br />
**openal<br />
<br />
* System<br />
**bytestring-mmap<br />
**directory<br />
**flepath<br />
**locale<br />
**time<br />
**parsedate<br />
**process<br />
**random<br />
**unix<br />
**parseargs</div>Gwernhttps://wiki.haskell.org/index.php?title=Partial_signatures&diff=63945Partial signatures2021-02-06T15:19:52Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Lemming</p>
<hr />
<div>"The regular (full) [[type signature|signature]] of a function specifies the type of the<br />
function and -- if the type includes constrained type variables --<br />
enumerates all of the typeclass constraints. The list of the constraints<br />
may be quite large. Partial signatures help when:<br />
*we wish to add an extra constraint to the type of the function but we do not wish to explicitly write the type of the function and enumerate all of the typeclass constraints,<br />
*we wish to specify the type of the function and perhaps some of the constraints -- and let the typechecker figure out the rest of them. <br />
<br />
Contrary to a popular belief, both of the above are easily possible, in Haskell98."<br />
<br />
[http://okmij.org/ftp/Haskell/types.html#partial-sigs Partial signatures]<br />
<br />
[[Category:Idioms]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Parsers&diff=63944Parsers2021-02-06T15:19:51Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Nedervold</p>
<hr />
<div>[[Category:Libraries]]<br />
Language/File format Parsers in Haskell<br />
<br />
This page is intended to serve as a collection of links to various readily-available parsers, implemented in Haskell.<br />
<br />
== ASN.1 ==<br />
[[Parsec]] parser for large subset of ASN.1 grammar (circa 98): http://adept.linux.kiev.ua/repos/asn1/<br />
<br />
== E-mail/SMTP ==<br />
[[Parsec]] parsers for grammars from RFC2821 and RFC2822 : http://cryp.to/hsemail/<br />
<br />
== Javascript ==<br />
[[Parsec]] parser for Javascript 1.5: [[Libraries_and_tools/HJS]]<br />
<br />
== JSON ==<br />
[[Parsec]] parser for JSON: http://www.tom.sfc.keio.ac.jp/~sakai/d/data/200604/JSON.hs<br />
<br />
Another [[Parsec]] parser for JSON: http://snippets.dzone.com/posts/show/3660<br />
<br />
== Other places to look ==<br />
Make sure you visited [[Applications_and_libraries/Compilers_and_interpreters]].<br />
<br />
Found a parser which I forgot to mention? Add link here.</div>Gwernhttps://wiki.haskell.org/index.php?title=Functii_din_Prelude,_A-F&diff=63943Functii din Prelude, A-F2021-02-06T15:19:50Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Ha$kell</p>
<hr />
<div>[[Category:Ro]] <br />
[[Image:Haskelllogo-small-flag-RO-8.jpg|center|Haskell - Un limbaj functional pur]]<br />
<br />
<br />
Lista de functii des folosite, cu nume de la A la F.<br />
Pentru a vedea un exemplu de folosire (si tipul fiecarei functii) cautati numele ei mai jos pe pagina, cu Find-ul browser-ului.<br />
<br />
abs - valoarea absoluta<br />
<br />
all - predicatul e adevarat pe toata lista de argumente ?<br />
<br />
and - conjunctie generalizata pe o lista de valori de tip Bool<br />
<br />
any - exista o valoare pe lista care satisface predicatul (in engleza aceste intrebari se pun cu any)<br />
<br />
atan - arctangenta<br />
<br />
break - rupe o lista inaintea locului/elementului care satisface un predicat<br />
<br />
ceiling - rotunjirea superioara la un intreg<br />
<br />
chr - caracterul cu acel cod ascii, conversie numar - caracter<br />
<br />
concat - concatenarea unui grup de liste , dat ca lista :) de liste<br />
<br />
cos - cosinusul<br />
<br />
digitToInt - transforma caracterul (daca e cifra) cifra in valoarea lui<br />
<br />
div - impartirea intreaga<br />
<br />
drop - arunca primele dintr-o lista<br />
<br />
dropWhile - arunca primele care indeplinesc conditia<br />
-- folositor la a ajunge la primele elemente semnificative daca pui conditia invers<br />
<br />
elem - apartine listei<br />
<br />
error - genereaza eroare si poate avea orice tip, folositi-o deci oriunde<br />
exp - e(x)<br />
<br />
flip - schimba ordinea argumentelor unei functii cu doua arg<br />
<br />
filter - alege ce satisface predicatul, din lista data<br />
<br />
----<br />
<haskell> <br />
:t abs<br />
abs :: Num a => a -> a<br />
<br />
Prelude> abs -9<br />
ERROR - Illegal Haskell 98 class constraint in inferred type<br />
*** Expression : abs - 9<br />
*** Type : (Num a, Num (a -> a)) => a -> a<br />
<br />
Prelude> abs (-9)<br />
9<br />
Prelude> abs (-9.3)<br />
9.3<br />
Prelude> <br />
----<br />
Prelude> :t all<br />
all :: (a -> Bool) -> [a] -> Bool<br />
Prelude> all isDigit "12234678"<br />
True<br />
Prelude> all isDigit "danu"<br />
False<br />
Prelude> <br />
----<br />
lse<br />
Prelude> :t and<br />
and :: [Bool] -> Bool<br />
Prelude> and [True,True ,True]<br />
True<br />
Prelude> and [True,True ,True,False]<br />
False<br />
Prelude> <br />
----<br />
Prelude> :t atan<br />
atan :: Floating a => a -> a<br />
Prelude> <br />
Prelude> 4 * atan 1<br />
3.14159<br />
----<br />
relude> :t break<br />
break :: (a -> Bool) -> [a] -> ([a],[a])<br />
Prelude> break isDigit "R2D2"<br />
("R","2D2")<br />
Prelude> break isDigit "3PO"<br />
("","3PO")<br />
Prelude> <br />
Prelude> break isSpace "La Multi Ani 2008!"<br />
("La"," Multi Ani 2008!")<br />
Prelude> <br />
Prelude> break (==0) [5,24,23,2,1,0,-1]<br />
([5,24,23,2,1],[0,-1])<br />
Prelude> <br />
----<br />
Prelude> :t ceiling<br />
ceiling :: (RealFrac a, Integral b) => a -> b<br />
Prelude> ceiling 2.2<br />
3<br />
Prelude> ceiling 1.242<br />
2<br />
Prelude> ceiling 1.42<br />
2<br />
Prelude> <br />
----<br />
Prelude> :t chr<br />
chr :: Int -> Char<br />
<br />
Prelude> chr 66<br />
'B'<br />
Prelude> chr 65<br />
'A'<br />
Prelude> chr 32<br />
' '<br />
Prelude> <br />
----<br />
Prelude> :t concat<br />
concat :: [[a]] -> [a]<br />
Prelude> concat ["La", "Multi", "Ani","!"]<br />
"LaMultiAni!"<br />
Prelude> <br />
----<br />
Prelude> :t cos<br />
cos :: Floating a => a -> a<br />
Prelude> cos 0<br />
1.0<br />
Prelude> <br />
----<br />
relude> digitToInt "0"<br />
ERROR - Type error in application<br />
*** Expression : digitToInt "0"<br />
*** Term : "0"<br />
*** Type : String<br />
*** Does not match : Char<br />
<br />
Prelude> digitToInt '0'<br />
0<br />
Prelude> digitToInt '1'<br />
1<br />
Prelude> digitToInt '2'<br />
2<br />
Prelude> digitToInt '3'<br />
3<br />
Prelude> digitToInt '4'<br />
4<br />
Prelude> digitToInt 'u'<br />
<br />
Program error: Char.digitToInt: not a digit<br />
<br />
Prelude> <br />
----<br />
Prelude> :t div<br />
div :: Integral a => a -> a -> a<br />
Prelude> 10 `div` 3<br />
3<br />
Prelude> <br />
----<br />
Prelude> :t drop<br />
drop :: Int -> [a] -> [a]<br />
Prelude> drop 2 ["La", "Multi", "Ani","!"]<br />
["Ani","!"]<br />
Prelude> <br />
-----<br />
Prelude> :t dropWhile<br />
dropWhile :: (a -> Bool) -> [a] -> [a]<br />
Prelude> dropWhile (==0) [0,0,0,0,1,2,3,4,0,0,1,2]<br />
[1,2,3,4,0,0,1,2]<br />
Prelude> <br />
Prelude> :t elem<br />
elem :: Eq a => a -> [a] -> Bool<br />
Prelude> elem "!" ["La", "Multi", "Ani","!"]<br />
True<br />
Prelude> elem "2008" ["La", "Multi", "Ani","!"]<br />
False<br />
Prelude> elem "2000" ["La", "Multi", "Ani","!"]<br />
False<br />
Prelude> <br />
----<br />
Prelude> :t error<br />
error :: String -> a<br />
Prelude> error "Stop the train!"<br />
ERROR - Cannot find "show" function for:<br />
*** Expression : error "Stop the train!"<br />
*** Of type : a<br />
<br />
Prelude> error "Stop the train!" :Char<br />
ERROR - Undefined constructor function "Char"<br />
Prelude> error "Stop the train!" :: String<br />
"<br />
Program error: Stop the train!<br />
<br />
Prelude> <br />
----<br />
Prelude> :t exp<br />
exp :: Floating a => a -> a<br />
Prelude> exp 1<br />
2.71828<br />
Prelude> <br />
----<br />
Prelude> :t flip<br />
flip :: (a -> b -> c) -> b -> a -> c<br />
Prelude> (flip (>)) 1 2<br />
True<br />
Prelude> <br />
----<br />
Prelude> :t filter<br />
filter :: (a -> Bool) -> [a] -> [a]<br />
Prelude> filter (>2) [1,2,3,4,1]<br />
[3,4]<br />
Prelude> <br />
<br />
</haskell><br />
<br />
----<br />
Pagina indexata la indexul [[Category:Ro]] [http://www.haskell.org/haskellwiki/Category:Ro Categories:Ro]<br />
----<br />
[http://www.haskell.org/haskellwiki/Ro/Haskell <= Inapoi la pagina principala Ro/Haskell. ]<br> <br><br />
[http://www.haskell.org/haskellwiki/Intrebarile_incepatorului <'''-''' Inapoi la Intrebarile incepatorului Ro/Haskell. ]</div>Gwernhttps://wiki.haskell.org/index.php?title=PreludeTour&diff=63941PreludeTour2021-02-06T15:19:49Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Bjpop</p>
<hr />
<div>== A Tour of the Haskell Prelude ==<br />
<br />
<br />
;<span id="abs">'''abs'''</span>:<br />
{| border="0" cellpadding="4"<br />
|-<br />
| ''type:'' || <hask>abs :: Num a => a -> a</hask><br />
|-<br />
| ''description:'' || returns the absolute value of a number.<br />
|-<br />
| ''definition:''<br />
| <haskell><br />
abs x<br />
| x >= 0 = x<br />
| otherwise = -x<br />
</haskell><br />
|- <br />
| ''usage:''<br />
| <pre><br />
Prelude> abs (-3)<br />
3<br />
</pre><br />
|}<br />
<br />
;<span id="all">'''all'''</span>:<br />
{| border="0" cellpadding="4"<br />
|-<br />
| ''type:'' || <hask>all :: (a -> Bool) -> [a] -> Bool</hask><br />
|-<br />
| ''description:'' || Applied to a predicate and a list, returns True if all elements of the list satisfy the predicate, and False otherwise. Similar to the function [[#any]].<br />
|-<br />
| ''definition:''<br />
| <haskell><br />
all p xs = and (map p xs)<br />
</haskell><br />
|- <br />
| ''usage:''<br />
| <pre><br />
Prelude> all (<11) [1..10]<br />
True<br />
Prelude> all isDigit "123abc"<br />
False<br />
</pre><br />
|}</div>Gwernhttps://wiki.haskell.org/index.php?title=PkgEnv&diff=63942PkgEnv2021-02-06T15:19:49Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Paolosi</p>
<hr />
<div>== PkgEnv ==<br />
<br />
=== Session Example ===<br />
<br />
We start creating a new package environment:<br />
<br />
<pre><br />
hypermac:trash paolo$ pkgenv binary.env<br />
Using GHC 6.10.1 (full path: /opt/local/bin/ghc-6.10.1)<br />
Using cabal-install 0.6.2 (full path: /Users/paolo/.cabal/bin/cabal)<br />
Installing package environment in /Users/paolo/trash/binary.env.<br />
Done!<br />
<br />
Usage:<br />
<br />
bash> source /Users/paolo/trash/binary.env/bin/activate<br />
(binary.env)bash> deactivate<br />
bash><br />
hypermac:trash paolo$ <br />
</pre><br />
<br />
We activate the new environment (the bash prompt is changed accordingly):<br />
<br />
<pre><br />
hypermac:trash paolo$ source binary.env/bin/activate <br />
(binary.env)hypermac:trash paolo$<br />
</pre><br />
<br />
All tools run now by default on the system package DB and the<br />
newly created/empty user package DB:<br />
<br />
<pre><br />
(binary.env)hypermac:trash paolo$ ghc-pkg list<br />
/opt/local/lib/ghc-6.10.1/./package.conf:<br />
Cabal-1.6.0.1, HUnit-1.2.0.3, QuickCheck-1.2.0.0, array-0.2.0.0,<br />
base-3.0.3.0, base-4.0.0.0, bytestring-0.9.1.4, containers-0.2.0.0,<br />
directory-1.0.0.2, (dph-base-0.3), (dph-par-0.3),<br />
(dph-prim-interface-0.3), (dph-prim-par-0.3), (dph-prim-seq-0.3),<br />
(dph-seq-0.3), editline-0.2.1.0, filepath-1.1.0.1, (ghc-6.10.1),<br />
ghc-prim-0.1.0.0, haddock-2.3.0, haskell-src-1.0.1.3,<br />
haskell98-1.0.1.0, hpc-0.5.0.2, html-1.0.1.2, integer-0.1.0.0,<br />
mtl-1.1.0.2, network-2.2.0.1, old-locale-1.0.0.1, old-time-1.0.0.1,<br />
packedstring-0.1.0.1, parallel-1.1.0.0, parsec-2.1.0.1,<br />
pretty-1.0.1.0, process-1.0.1.0, random-1.0.0.1,<br />
regex-base-0.72.0.2, regex-compat-0.71.0.1, regex-posix-0.72.0.3,<br />
rts-1.0, stm-2.1.1.2, syb-0.1.0.0, template-haskell-2.3.0.0,<br />
time-1.1.2.2, unix-2.3.1.0, xhtml-3000.2.0.1<br />
/Users/paolo/trash/binary.env/ghc-packages.conf:<br />
</pre><br />
<br />
Let's install a package inside the new environment:<br />
<br />
<pre><br />
(binary.env)hypermac:trash paolo$ cabal install --verbose=0 binary<br />
Reading package info from "dist/installed-pkg-config" ... done.<br />
Writing new package config file... done.<br />
(binary.env)hypermac:trash paolo$ ghc-pkg list<br />
/opt/local/lib/ghc-6.10.1/./package.conf:<br />
Cabal-1.6.0.1, HUnit-1.2.0.3, QuickCheck-1.2.0.0, array-0.2.0.0,<br />
base-3.0.3.0, base-4.0.0.0, bytestring-0.9.1.4, containers-0.2.0.0,<br />
directory-1.0.0.2, (dph-base-0.3), (dph-par-0.3),<br />
(dph-prim-interface-0.3), (dph-prim-par-0.3), (dph-prim-seq-0.3),<br />
(dph-seq-0.3), editline-0.2.1.0, filepath-1.1.0.1, (ghc-6.10.1),<br />
ghc-prim-0.1.0.0, haddock-2.3.0, haskell-src-1.0.1.3,<br />
haskell98-1.0.1.0, hpc-0.5.0.2, html-1.0.1.2, integer-0.1.0.0,<br />
mtl-1.1.0.2, network-2.2.0.1, old-locale-1.0.0.1, old-time-1.0.0.1,<br />
packedstring-0.1.0.1, parallel-1.1.0.0, parsec-2.1.0.1,<br />
pretty-1.0.1.0, process-1.0.1.0, random-1.0.0.1,<br />
regex-base-0.72.0.2, regex-compat-0.71.0.1, regex-posix-0.72.0.3,<br />
rts-1.0, stm-2.1.1.2, syb-0.1.0.0, template-haskell-2.3.0.0,<br />
time-1.1.2.2, unix-2.3.1.0, xhtml-3000.2.0.1<br />
/Users/paolo/trash/binary.env/ghc-packages.conf:<br />
binary-0.4.4<br />
</pre><br />
<br />
We can now use the new package:<br />
<br />
<pre><br />
(binary.env)hypermac:trash paolo$ ghci<br />
GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help<br />
Loading package ghc-prim ... linking ... done.<br />
Loading package integer ... linking ... done.<br />
Loading package base ... linking ... done.<br />
Prelude> import Data.Binary<br />
Prelude Data.Binary><br />
</pre><br />
<br />
and leave the environment:<br />
<br />
<pre><br />
(binary.env)hypermac:trash paolo$ deactivate <br />
hypermac:trash paolo$ <br />
</pre><br />
<br />
and when you're done with the environment, simply remove it:<br />
<br />
<pre><br />
hypermac:trash paolo$ rm -rf binary.env<br />
</pre></div>Gwernhttps://wiki.haskell.org/index.php?title=Poorly_named_things&diff=63940Poorly named things2021-02-06T15:19:48Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Gwern</p>
<hr />
<div>* forkOS - forkOS does not create an OS-level thread. It creates a lightweight thread, the same as forkIO. The only difference is when you are doing FFI.<br />
* return - Does not return a value from a function, rather 'returns' a value into a monad. Don't know what a better name would be, though. 'monadificate'?<br />
:'seal'? 'monadify'? 'monify'? 'coat'? --[[User:Gwern|Gwern]] 18:25, 5 April 2010 (UTC)</div>Gwernhttps://wiki.haskell.org/index.php?title=CouchDB&diff=63938CouchDB2021-02-06T15:19:47Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Andrewufrank</p>
<hr />
<div>= CouchDB =<br />
<br />
[[Category:Packages]]<br />
<br />
CouchDB Haskell package is the Haskell interface to the couchDB database software. I appreciate the efforts of Arjun Guha and Brendan Hickey to construct this interface. I think it is an improvement over the original and most convenient to use!<br />
<br />
CouchDB is a document oriented datastorage system (with versions) which is geared towards replication. For more information read Anderson, Lehnardt and Slater's book "CouchDB - The definite guide" ([http://books.couchdb.org/relax/]).<br />
<br />
Examples how to use the Haskell CouchDB interface are not easy to find on the web. I found only one [http://www.maztravel.com/haskell/mySqlToCouchDB.html], which is probably compiled with an slightly earlier version of CouchDB than the current 0.10.1.<br />
<br />
I created this wiki page to make available the simple examples I coded to learn to use CouchDB and to report of some of the not-so-obvious traps beginners could fall into.<br />
<br />
= Example: Store and retrieve notes =<br />
<br />
The simple example I selected is the database backend of a "note" application (e.g. Tomboy or any other of the yellow paste-it notes look-alike). The first function is to store a note, as an example on how to store data in couch:<br />
<br />
== Store note ==<br />
<br />
Here the code for storing a note and retrieving it with the doc id:<br />
<haskell> <br />
{-# LANGUAGE DeriveDataTypeable<br />
, ScopedTypeVariables #-}<br />
<br />
module Notes1 where<br />
<br />
import Database.CouchDB (getDoc, newDoc, runCouchDB', db, Rev(..), Doc)<br />
import Data.Data (Data, Typeable)<br />
<br />
import Text.JSON<br />
import Text.JSON.Pretty (pp_value)<br />
import Text.JSON.Pretty (render)<br />
import Text.JSON.Generic (toJSON, fromJSON)<br />
<br />
type Strings = [String] -- basic<br />
<br />
data Note = Note {title, text :: String, tags :: Strings}<br />
deriving (Eq, Ord, Show, Read , Typeable, Data) -- not yet necessary<br />
<br />
------ copied from henry laxon<br />
<br />
ppJSON = putStrLn . render . pp_value<br />
<br />
justDoc :: (Data a) => Maybe (Doc, Rev, JSValue) -> a<br />
justDoc (Just (d,r,x)) = stripResult (fromJSON x)<br />
where stripResult (Ok z) = z<br />
stripResult (Error s) = error $ "JSON error " ++ s<br />
justDoc Nothing = error "No such Document"<br />
<br />
--------------------------------<br />
mynotes = db "firstnotes1"<br />
<br />
n0 = Note "a59" "a1 text vv 45" ["tag1"]<br />
<br />
n1 = Note "a56" "a1 text vv 45" ["tag1"]<br />
n2 = Note "a56" "updated a1 text vv 45" ["tag1"]<br />
<br />
n1j = toJSON n1 -- convNote2js n1<br />
<br />
runNotes1 = do<br />
(doc1, rev1) <- runCouchDB' $ newDoc mynotes n1j<br />
putStrLn $ "stored note" ++ show doc1 ++ " revision " ++ show rev1<br />
Just (_,_,jvalue) <- runCouchDB' $ getDoc mynotes doc1<br />
ppJSON jvalue<br />
<br />
jstuff <- runCouchDB' $ getDoc mynotes doc1<br />
let d = justDoc jstuff :: Note<br />
putStrLn $ "found " ++ show d<br />
return ()<br />
<br />
-- the output is:<br />
--stored noteaa45700981408039346f9c8c73f8701f <br />
-- revision 1-7fa1d1116e6ae0c1ee8d4ce89a701fdf<br />
--{"_id": "aa45700981408039346f9c8c73f8701f",<br />
-- "_rev": "1-7fa1d1116e6ae0c1ee8d4ce89a701fdf", "title": "a56",<br />
-- "text": "a1 text vv 45", "tags": ["tag1"]}<br />
--found Note {title = "a56", text = "a1 text vv 45", tags = ["tag1"]}<br />
<br />
</haskell><br />
<br />
== Multiple functions to store and retrieve notes ==<br />
Notes have a title, a text and a set of tags. We need functions to store a new note, to update the content of a note and to retrieve all notes with a given word in the title, in the text or as a tag; each of these functions return a list of pairs (doc_id, title) from which the correct one is selected and then retrieved with the doc_id.<br />
<br />
I have decided that the notes have IDs produced by couchDB; this assures that changes, even changes in title, continue the same object with a new version.<br />
<br />
<haskell><br />
<br />
{-# LANGUAGE DeriveDataTypeable<br />
, ScopedTypeVariables #-}<br />
<br />
module Notes2 (storeNewNote<br />
, changeNoteContent<br />
, updateNote<br />
, deleteNote<br />
, retrieveNote<br />
, findNoteByTitle<br />
, findNoteByTag<br />
, findNoteByContent ) where<br />
<br />
import Database.CouchDB<br />
(rev, deleteDoc, CouchView(..), newView, Doc(..), isDocString,<br />
queryView, getAndUpdateDoc, DB(..), getDoc, newDoc, db, doc,<br />
newNamedDoc, runCouchDB', Rev(..))<br />
-- , couchViewToJSON)<br />
<br />
import Data.Data (Data, Typeable)<br />
<br />
import Text.JSON<br />
import Text.JSON.Pretty (pp_value)<br />
import Text.JSON.Pretty (render)<br />
import Database.CouchDB.JSON (jsonObject)<br />
import Text.JSON.Generic (toJSON, fromJSON)<br />
<br />
type Strings = [String] -- basic<br />
<br />
-- from Henry Laxen's code:<br />
<br />
type QueryViewResult = (Database.CouchDB.Doc,JSValue)<br />
<br />
ppJSON = putStrLn . render . pp_value<br />
<br />
justDoc :: (Data a) => Maybe (Database.CouchDB.Doc, Rev, JSValue) -> a<br />
justDoc (Just (d,r,x)) = stripResult (fromJSON x)<br />
where stripResult (Ok z) = z<br />
stripResult (Error s) = error $ "JSON error " ++ s<br />
justDoc Nothing = error "No such Document"<br />
<br />
-----<br />
docid_doc :: (Data a) => QueryViewResult -> (Doc, a)<br />
docid_doc (d, x) = (d, stripResult . fromJSON $ x)<br />
where stripResult (Ok z) = z<br />
stripResult (Error s) = error $ "JSON error " ++ s<br />
<br />
--------------------- some example data<br />
<br />
mynotes = db mynotesString<br />
mynotesString = "firstnotes1" -- the name of the couchdb <br />
<br />
n0 = Note "a59" "a1 text vv 45" ["tag1", "tag2"]<br />
<br />
n1 = Note "a56" "a1 text vv 45" ["tag1", "tag3"]<br />
n2 = Note "a56" "updated a1 text vv 45" ["tag1", "tag2", "tag4"]<br />
<br />
-------------------------------<br />
<br />
data Note = Note {title, text :: String, tags :: Strings}<br />
deriving (Eq, Ord, Show, Read , Typeable, Data) -- not yet necessary<br />
<br />
storeNewNote :: DB -> Note -> IO ()<br />
storeNewNote db note = do<br />
let jnote = toJSON note -- the ID is set by couchdb<br />
(doc, rev) <- runCouchDB' $ newDoc db jnote<br />
putStrLn $ "stored note" ++ show doc ++ " " ++ show rev<br />
return ()<br />
<br />
<br />
changeNoteContent :: DB -> Doc -> Note -> IO ()<br />
changeNoteContent db docid newnote = do <br />
ret <- runCouchDB' $ getAndUpdateDoc db (docid) (updateNote newnote)<br />
let rev = maybe (error "update did not succeed") id ret<br />
putStrLn $ "changed " ++ show rev<br />
return ()<br />
<br />
updateNote :: Note -> JSValue -> IO JSValue<br />
updateNote new old = return . const (toJSON new) $ old<br />
<br />
deleteNote :: DB -> Doc -> Rev -> IO ()<br />
deleteNote db id r = do<br />
ret <- runCouchDB' $ deleteDoc db (id, r) <br />
putStrLn $ "deleted " ++ show ret<br />
return ()<br />
<br />
retrieveNote :: DB -> Doc -> IO Note <br />
retrieveNote db docid = do<br />
ret <- runCouchDB' $ getDoc db docid -- :: Maybe (Doc, Rev, JSValue)<br />
-- assumes the note title is the key<br />
let n = justDoc ret :: Note<br />
putStrLn $ "stored note" ++ show n<br />
return n<br />
<br />
findNoteByTitle :: DB -> String -> IO [(Doc, Note)]<br />
findNoteByTitle db tit = do<br />
putStrLn $ "search by title using view 'titles' " ++ show tit<br />
ret :: [QueryViewResult] <- runCouchDB' $ do<br />
queryView db (doc designdoc) (doc "bytitle") [("key", toJSON tit)]<br />
putStrLn $ show ret<br />
let ls = map docid_doc ret<br />
putStrLn $ "result " ++ show ls<br />
return ls<br />
<br />
findNoteByTag :: DB -> String -> IO [(Doc, Note)]<br />
findNoteByTag db ta = do<br />
putStrLn $ "search by title using view 'titles' " ++ show ta<br />
ret :: [QueryViewResult] <- runCouchDB' $ do<br />
queryView db (doc designdoc) (doc "bytags") [("key", toJSON ta)]<br />
putStrLn $ show ret<br />
let ls = map docid_doc ret<br />
putStrLn $ "result " ++ show ls<br />
return ls<br />
<br />
findNoteByContent :: DB -> String -> IO [(Doc, Note)]<br />
findNoteByContent db word = do<br />
putStrLn $ "search by title using view 'titles' " ++ show word<br />
ret :: [QueryViewResult] <- runCouchDB' $ do<br />
queryView db (doc designdoc) (doc "bywords") [("key", toJSON word)]<br />
putStrLn $ show ret<br />
let ls = map docid_doc ret<br />
putStrLn $ "result " ++ show ls<br />
return ls<br />
<br />
--------------------------------------------------<br />
<br />
titleView = "function(doc) { if (doc.title && doc.text && doc.tags) \<br />
\ {emit(doc.title, doc._id); } }"<br />
titleView2 = ViewMap "bytitle" titleView<br />
<br />
<br />
tagView = "function(doc) { if (doc.title && doc.text && doc.tags) \<br />
\ { var len=doc.tags.length; \<br />
\ for(var i=0; i<len; i++) { \<br />
\ var value = doc.tags[i]; \<br />
\ emit(value, doc._id); } \<br />
\ } \<br />
\ }"<br />
-- tried in temporary views of Futon<br />
<br />
tagView2 = ViewMap "bytags" tagView<br />
<br />
wordView = "function (doc) { if (doc.title && doc.text && doc.tags) \<br />
\ { var words = doc.text.split (' '); \ <br />
\ var len=words.length; \<br />
\ for(var i=0; i<len; i++) { \<br />
\ var value = words[i]; \<br />
\ emit(value, doc._id); } \<br />
\ } \<br />
\ }"<br />
-- use ' for strings inside a haskell string<br />
-- escapes are not removed when converting to JSON ?<br />
<br />
wordView2 = ViewMap "bywords" wordView <br />
<br />
--- setting views:<br />
designdoc = "five" -- "six" -- change for each edit -- cannot update!<br />
<br />
setViews dbstring = do<br />
r <- runCouchDB' $ newView dbstring designdoc [titleView2, tagView2, wordView2]<br />
-- inconsistency: here a string, not a DB type !<br />
putStrLn $ "view stored"<br />
return ()<br />
----<br />
<br />
run2 = do<br />
storeNewNote mynotes n0<br />
retrieveNote mynotes (doc "c4bf00e96e2446ce1508ba055e9b7ef6")<br />
changeNoteContent mynotes (doc "c4bf00e96e2446ce1508ba055e9b7ef6") n2<br />
retrieveNote mynotes (doc "c4bf00e96e2446ce1508ba055e9b7ef6")<br />
return ()<br />
<br />
--stored note68d5cfa3622c4586a7a1bfc695e72765 1-dee34e8ccb4ef3ceb9a7dcfb3d7cd20d<br />
--stored noteNote {title = "a1234", text = "a1 text vv 45", tags = ["tag1"]}<br />
--changed 2-53bfc49b385805020194a59b39fd5ffb<br />
--stored noteNote {title = "a56", text = "updated a1 text vv 45", tags = ["tag1","tag2","tag4"]}<br />
<br />
-- error when duplicate is not appropriate:<br />
--stored note"\"*** Exception: src/Database/CouchDB/Unsafe.hs:80:10-63: Irrefutable pattern failed for pattern (Text.JSON.Types.JSObject errorObj)<br />
<br />
run3 :: IO () = do<br />
setViews mynotesString<br />
return ()<br />
<br />
run4 :: IO () = do <br />
ls :: [(Doc, Note)] <- findNoteByTitle mynotes "a55"<br />
putStrLn $ "found by title " ++ show ls<br />
return ()<br />
<br />
<br />
</haskell><br />
<br />
<br />
Notice that the syntax for retrieval has changed since the example code for "converting from MySQL to CouchDB" was written: no preceeding "/_design/" in the name of the view.<br />
<br />
= A few suggestions for improvement in the interface<br />
Most annoying is that design documents cannot be updated; a new set must be stored with a new name. A function updateView would be useful.<br />
The type of newView is not consistent with the other calls - it requires the name of the couchDB as a String, not a DB type.<br />
I used couchViewToJSON to test the views i wrote - it could be useful to export it.<br />
<br />
<br />
= Coda =<br />
I do not guarantee for the correctness of the code (of course). I hope it is useful. I invite others to contribute their examples or more complex codes so we can learn from each other. <br />
<br />
I am currently working on using couchDB and interested to hear comments at frank at geoinfo dot tuwien dot ac dot at.</div>Gwernhttps://wiki.haskell.org/index.php?title=Stanamic_typing&diff=63939Stanamic typing2021-02-06T15:19:47Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by DonStewart</p>
<hr />
<div>"We describe a datatype of polymorphic balanced binary trees: AVL trees.<br />
The trees are polymorphic: the values in different nodes may have<br />
different type. The trees are balanced: for each non-leaf node, the<br />
heights of its two children can differ at most by one. Here, by<br />
definition the height of a node is 1 + max of the heights of its<br />
children. A leaf node has the height of 0.<br />
<br />
The main feature of the present approach is a blended static and dynamic<br />
enforcement of the balancing constraint. The function make_node<br />
verifies the balancing constraint at compile time -- if it can. If the<br />
static check is not possible, the function delays the check till the<br />
run-time"<br />
<br />
[http://okmij.org/ftp/Haskell/types.html#stanamic-AVL Polymorphic stanamically balanced AVL trees]<br />
<br />
[[Category:Idioms]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Scrolls_of_lambda&diff=63937Scrolls of lambda2021-02-06T15:19:46Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Roconnor</p>
<hr />
<div>[[Category:Humor]]<br />
<br />
== Lambda prayer ==<br />
<br />
Oh holy father who lives in the lambda.<br />
May your free variables stay unbound. liftM our minds into a higher StateT and let us find enlightenment. Deliver us from impurity, thy monad is great. Amen.<br />
<br />
== Lambda warrior prayer: ==<br />
<br />
Oh holy father who lives in the lambda.<br />
Let the arrows consume my enemies, guard me from exhaustion and return me home safely. Amen.</div>Gwernhttps://wiki.haskell.org/index.php?title=Type_variables_instead_of_concrete_types&diff=63936Type variables instead of concrete types2021-02-06T15:19:44Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Lemming</p>
<hr />
<div>If you are new to Haskell you may think that type variables and [[polymorphism]] are fancy things that are rarely used.<br />
Maybe you are surprised that type variables and [[type class]] constraints can increase safety and readability<br />
also if you are eventually using only one concrete type.<br />
<br />
Imagine the [[Prelude]] would contain the following functions:<br />
<haskell><br />
maximum :: [Integer] -> Integer<br />
sum :: [Integer] -> Integer<br />
</haskell><br />
Sure, the names are carefully chosen and thus you can guess what they do.<br />
But the signature is not as expressive as it could be.<br />
Indeed these functions are in the Prelude but with a more general signature.<br />
<haskell><br />
maximum :: (Ord a) => [a] -> a<br />
sum :: (Num a) => [a] -> a<br />
</haskell><br />
These functions can also be used for <hask>Integer</hask>s,<br />
but the signatures show which aspects of integers are actually required.<br />
We realize that <hask>maximum</hask> is not about numbers, but can also be used for other ordered types, like <hask>Char</hask>.<br />
We can also conclude that <hask>maximum []</hask> is undefined,<br />
since the <hask>Ord</hask> class has no function to construct certain values and the input list does not contain an element of the required type.<br />
<br />
<br />
Now consider that you have a complex function that is hard to understand.<br />
It is fixed to a concrete type, say <hask>Double</hask>.<br />
You want to divide that function into a function that does the processing of the structure<br />
and another function which does the calculations with <hask>Double</hask>.<br />
This is good style in the sense of the "[[Separation of concerns]]" idiom.<br />
You do it, because you want to untangle the [[Things_to_avoid#Avoid_explicit_recursion|explicit recursion]],<br />
which is hard to understand of its own,<br />
and the calculation, which also has pitfalls.<br />
The structure processing does not know about the <hask>Double</hask><br />
and it is wise to use type variables instead of <hask>Double</hask><br />
<br />
Making the example more concrete, look at a state monad transformer <hask>StateT</hask><br />
which shall be nested by a nesting depth that is only known at runtime.<br />
Ok that's not possible, so just consider a <hask>State</hask> [[applicative functor]], that shall be nested the same way.<br />
The functor depends on an input of the same type as its functor output,<br />
that is we nest functions of type <hask>(Double -> State Double Double)</hask>.<br />
The nested functor has a list of state values as state value.<br />
The nesting depth depends on the length of the list of state values.<br />
(This design also forbids transformer techniques for general applicative functors.)<br />
We could write a nesting function fixed to type <hask>Double</hask><br />
<haskell><br />
stackStates :: (Double -> State Double Double) -> (Double -> State [Double] Double)<br />
</haskell><br />
but it is too easy to mix up state and return value here, because they have the same type.<br />
You should really separate that<br />
<haskell><br />
stackStates :: (a -> State s a) -> (a -> State [s] a)<br />
stackStates m = State . List.mapAccumL (runState . m)<br />
</haskell><br />
also if you only use it for <hask>Double</hask>.<br />
This way the type checker asserts, that you never mix up the state with the other type.<br />
<br />
<br />
[[Category:Style]]<br />
[[Category:Idioms]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Untypeable_Haskell_98&diff=63935Untypeable Haskell 982021-02-06T15:19:43Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by DonStewart</p>
<hr />
<div>Here we document code that looks like it should be valid Haskell98, but<br />
isn't typeable without extensions:<br />
<br />
<haskell><br />
f :: a -> a<br />
f x = g x<br />
where<br />
-- g :: a -> a<br />
g y = bind x y<br />
<br />
bind :: a -> a -> a<br />
bind a b = a<br />
</haskell><br />
<br />
The above Haskell code is Haskell 98, rank-1 types, but cannot be given a type signature. Try commenting out the type signature for g and everything will go wrong.<br />
<br />
In GHC making the type of f :: forall a . a -> a, and adding -fglasgow-exts will make this code work. No such luck in Hugs.<br />
<br />
With pattern type annotations, however, the code works in both Hugs and GHC:<br />
<br />
<haskell><br />
f :: a -> a<br />
f (x :: a) = g x<br />
where<br />
g :: a -> a<br />
g y = bind x y<br />
<br />
bind :: a -> a -> a<br />
bind a b = a<br />
</haskell><br />
<br />
[[Category:Proposals]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Untypechecking&diff=63934Untypechecking2021-02-06T15:19:42Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by DonStewart</p>
<hr />
<div>== Untypechecking ==<br />
<br />
Converting from a type to a term.<br />
<br />
<pre><br />
[Haskell] De-typechecker: converting from a type to a term<br />
<br />
oleg at pobox.com oleg at pobox.com<br />
Tue Mar 1 03:13:08 EST 2005<br />
<br />
* Next message: [Haskell] Re: Type of y f = f . f<br />
* Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]<br />
<br />
-----------------------------------------------------------------------------------------------------<br />
<br />
This message presents polymorphic functions that derive a term for a<br />
given type -- for a class of fully polymorphic functions: proper and<br />
improper combinators. This is better understood on an example:<br />
<br />
rtest4 f g = rr (undefined::(b -> c) -> (a -> b) -> a -> c) HNil f g<br />
*HC> rtest4 (:[]) Just 'x'<br />
[Just 'x']<br />
*HC> rtest4 Just Right True<br />
Just (Right True)<br />
<br />
We ask the Haskell typechecker to derive us a function of the<br />
specified type. We get the real function, which we can then apply to<br />
various arguments. The return result does behave like a `composition'<br />
-- which is what the type specifies. Informally, we converted from<br />
`undefined' to defined.<br />
<br />
It must be emphasized that no modifications to the Haskell compiler are<br />
needed, and no external programs are relied upon. In particular,<br />
however surprising it may seem, we get by without `eval' -- because<br />
Haskell has reflexive facilities already built-in.<br />
<br />
This message contains the complete code. It can be loaded as it is<br />
into GHCi -- tested on GHCi 6.2.1 or GHCi snapshot 6.3.20041106. It<br />
may take a moment or two to load though. Commenting our tests speeds<br />
up the loading.<br />
<br />
<br />
This message presents two different converters from a type to a term.<br />
Both derive a program, a term, from its specification, a type -- for<br />
a class of fully polymorphic functions. The first converter has just<br />
been demonstrated. It is quite limited in that the derived function<br />
must be used `polymorphically' -- distinct type variables must be<br />
instantiated to different types (or, the user should first<br />
instantiate their types and then derive the term). The second<br />
converter is far more useful: it can let us `visualize' what a<br />
function with a particular type may be doing. For example, it might<br />
not be immediately clear what the function of the type<br />
(((a -> b -> c) -> (a -> b) -> a -> c) -><br />
(t3 -> t1 -> t2 -> t3) -> t) -> t)<br />
<br />
is. The test (which is further down) says<br />
<br />
test9 = reify (undefined::(((a -> b -> c) -> (a -> b) -> a -> c) -><br />
(t3 -> t1 -> t2 -> t3) -> t) -> t) gamma0<br />
<br />
*HC> test9<br />
\y -> y (\d h p -> d p (h p)) (\d h p -> d)<br />
<br />
that is, the function in question is one of the X combinators. It is<br />
an improper combinator.<br />
<br />
A particular application is converting a point-free function into the<br />
pointful form to really understand the former. For example, it might<br />
take time to comprehend the following expression<br />
<br />
pz = (((. head . uncurry zip . splitAt 1 . repeat) . uncurry) .) . (.) . flip<br />
<br />
It is derived by Stephan Hohe in<br />
http://www.haskell.org/pipermail/haskell-cafe/2005-February/009146.html<br />
<br />
Our system says<br />
test_pz = reify (undefined `asTypeOf` pz) gamma0<br />
*HC> test_pz<br />
\h p y -> h y (p y)<br />
<br />
So, pz is just the S combinator.<br />
<br />
As an example below shows, an attempt to derive a term for a type<br />
a->b expectedly fails. The type error message essentially says that<br />
a |- b is underivable.<br />
<br />
<br />
Our system solves type habitation for a class of functions with<br />
polymorphic types. From another point of view, the system is a prover<br />
in the implication fragment of intuitionistic logic. Essentially we<br />
turn a _type_ into a logical program -- a set of Horn clauses -- which<br />
we then solve by SLD resolution. It is gratifying to see that<br />
Haskell typeclasses are up to that task.<br />
<br />
<br />
The examples above exhibit fully polymorphic types -- those with<br />
*uninstantiated* -- implicitly universally quantified -- type<br />
variables. That is, our typeclasses can reify not only types but also<br />
type schemas. The ability to operate on and compare *unground* types<br />
with *uninstantiated* type variables is often sought but rarely<br />
attained. The contribution of this message is the set of primitives<br />
for nominal equality comparison and deconstruction of unground<br />
types. Earlier these tools were used to implement nested monadic<br />
regions in the type-safe manner without imposing the total order on<br />
the regions. The monadic regions are described in the paper by M. Fluet<br />
and G. Morrisett, ICFP04.<br />
<br />
The rest of this message is as follows:<br />
<br />
- equality predicate of type schemas<br />
- function types as logic programs. Solving type habitation<br />
by SLD resolution<br />
- more examples<br />
- code<br />
-- class Resolve: SLD resolution<br />
<br />
* Equality predicate of type schemas<br />
<br />
This is a short remark on the equality predicate of type schemas. In<br />
more detail, this topic will be described elsewhere.<br />
<br />
To obtain the equality, we need the following overlapping instances<br />
extensions<br />
<br />
> {-# OPTIONS -fglasgow-exts #-}<br />
> {-# OPTIONS -fallow-undecidable-instances #-}<br />
> {-# OPTIONS -fallow-overlapping-instances #-}<br />
> {-# OPTIONS -fallow-incoherent-instances #-}<br />
><br />
> module HC where<br />
<br />
<br />
We must remark that -fallow-overlapping-instances and<br />
-fallow-incoherent-instances extensions are used *exclusively* for the<br />
type equality testing. With these extensions and the following declarations<br />
<br />
class C a where op:: a -> Int<br />
instance C a where ...<br />
instance C Bool where ...<br />
data W = forall a. W a<br />
<br />
the expression<br />
case W () of W x -> op x<br />
<br />
is well-typed with the "instance C a" chosen. In the context of TypeEq,<br />
that behavior guarantees that a quantified variable is equal only to itself<br />
and nothing else. So, the use of overlapping instances in this code<br />
is well-defined and sound.<br />
<br />
The existence of this remarkable feature has been pointed out by Simon<br />
Peyton-Jones, who implemented it.<br />
<br />
The code at the end of this message defines nominal equality on<br />
quantified type variables. A quantified variable is equal only to<br />
itself. It is useful to think of such type variables as being<br />
Skolemized. Fortunately, GHC kindly does all the Skolemization for<br />
us. For example,<br />
<br />
*FP> type'eq id id<br />
HFalse<br />
<br />
because the type of the identity function "a->a" means "forall a. a<br />
->a", which, after skolemization, becomes "sk1 -> sk1". The type of<br />
the second `id' in the above equation becomes "sk2 -> sk2" -- thus the<br />
types are not equal. Indeed, if we ask GHC to show us the inferred<br />
type of the above expression<br />
<br />
*FP> :t type'eq id id<br />
type'eq id id :: forall a a1 b. (TypeEq (a -> a) (a1 -> a1) b) => b<br />
<br />
we can see the Skolemization very clearly.<br />
<br />
OTH,<br />
*FP> let f x = (x,x) in case f id of (u,v) -> type'eq u v<br />
HTrue<br />
because<br />
*FP> :t let f x = (x,x) in case f id of (u,v) -> type'eq u v<br />
let f x ... :: forall a b. (TypeEq (a -> a) (a -> a) b) => b<br />
<br />
that is, the types of both `id' are unified (yet they remain unground)<br />
<br />
* Two type-to-term reifiers<br />
<br />
As we have mentioned, we introduce two type reifiers. The first one converts<br />
a type to the following term:<br />
<br />
> data Term = Var Int | L Int Term | A Term Term -- deriving Show<br />
<br />
The custom Show instance is at the end of this message. The second reifier<br />
converts a type to a true Haskell term. The difference between the reifiers<br />
is akin to the difference between a homogeneous list and a heterogeneous<br />
list (HList). The former reifier is far easier to explain.<br />
<br />
* Function types as logic programs. Solving type habitation by SLD resolution<br />
<br />
To solve the type habitation problem -- to find a term (proof) for a<br />
proposition expressed as a type -- we use SLD resolution. It may be<br />
helpful to think of the whole process as converting a type<br />
(proposition) into a Horn-clause logical program, and solving that<br />
program using a Prolog-style evaluator. Here are a few examples of<br />
types and the corresponding logical programs.<br />
<br />
The type a->b->a after applying the implication elimination rule twice<br />
yields the following program:<br />
<br />
t2t(a, var(1)).<br />
t2t(b, var(2)).<br />
?- t2t(a,X), Term = lambda(1,(lambda(2,X))).<br />
% solution: lambda(1, lambda(2, var(1))), or \x y -> x<br />
<br />
The type "(b -> c) -> (a -> b) -> a -> c" (of the composition function)<br />
corresponds to the following program:<br />
<br />
t2t(c,app(var(1),X)) :- t2t(b,X).<br />
t2t(b,app(var(2),X)) :- t2t(a,X).<br />
t2t(a,var(3)).<br />
?- t2t(c,X), Term = lambda(1,lambda(2,lambda(3,X))).<br />
% solution:<br />
% lambda(1, lambda(2, lambda(3, app(var(1), app(var(2), var(3))))))<br />
% or \x y z -> x (y z)<br />
<br />
<br />
The type of one of the X combinators [1] (which is an improper combinator)<br />
forall t a b c t1 t2 t3.<br />
(((a -> b -> c) -> (a -> b) -> a -> c) -> (t3 -> t1 -> t2 -> t3) -> t)<br />
-> t<br />
<br />
corresponds to the logical program<br />
<br />
t2t(t, app(app(var(1),X),Y)) :- t2t(u1,X), t2t(u2,Y).<br />
<br />
% u1 denotes (a -> b -> c) -> (a -> b) -> a -> c<br />
t2t(u1,X) :- t2t(c,Y), X = lambda(3,lambda(4,lambda(5,Y))).<br />
t2t(c,app(app(var(3),X),Y)) :- t2t(a,X), t2t(b,Y).<br />
t2t(b,app(var(4),X)) :- t2t(a,X).<br />
t2t(a,var(5)).<br />
<br />
% u2 denotes t3 -> t1 -> t2 -> t3<br />
t2t(u2,X) :- t2t(t3,Y), X = lambda(6,lambda(7,lambda(8,Y))).<br />
t2t(t3,var(6)).<br />
t2t(t1,var(7)).<br />
t2t(t2,var(8)).<br />
<br />
?- t2t(t,X), Term = lambda(1,X).<br />
<br />
The solution to the latter is, when printed nicely,<br />
\f -> f (\a b c -> (a c) (b c)) (\x y z -> x)<br />
<br />
<br />
We construct such programs and solve them with the ordinary SLD resolution<br />
-- only using Haskell typeclasses rather than Prolog.<br />
<br />
[1] Jeroen Fokker, The Systematic Construction of a One-combinator Basis for<br />
Lambda-Terms.<br />
Formal Aspects of Computing 4 (1992), pp. 776-780.<br />
http://www.cs.uu.nl/people/jeroen/article/combinat/combinat.ps<br />
<br />
<br />
* More examples<br />
<br />
The reification function takes, as one argument, an environment -- or<br />
the initial assumption. Oftentimes it is this:<br />
<br />
> gamma0 = G HNil 0<br />
<br />
Other environments may be used to reify *open* terms.<br />
<br />
We start with a few simple examples:<br />
<br />
> test1 = let term = \x y -> x in reify term gamma0<br />
> test2 = let term = \x y -> y in reify term gamma0<br />
> test3 = let term = \f x y -> f x in reify term gamma0<br />
><br />
> -- \f x y -> f y x<br />
> test4 = reify (__::(t -> t1 -> t2) -> t1 -> t -> t2) gamma0<br />
><br />
> -- \f g a b -> f (g a b)<br />
> test5 = let term = (.) (.) (.) in reify (undefined `asTypeOf` term) gamma0<br />
><br />
> pz = (((. head . uncurry zip . splitAt 1 . repeat) . uncurry) .) . (.) . flip<br />
> test_pz = reify (undefined `asTypeOf` pz) gamma0<br />
><br />
> -- \f g h x y -> f (g x) (h y)<br />
> test7 = let term = ((flip . ((.) .)) .) . (.) in reify term gamma0<br />
<br />
More complex are improper combinators:<br />
<br />
> -- \f -> f (\x -> x)<br />
> test6 = reify (__::((a->a)->b) -> b) gamma0<br />
><br />
> -- X combinators<br />
> {-- commented out to speed up loading<br />
> test8 = let term = \a b c d -> c d (a (\x -> d))<br />
> in reify (undefined `asTypeOf` term) gamma0<br />
><br />
> test9 = reify (undefined::(((a -> b -> c) -> (a -> b) -> a -> c) -><br />
> (t3 -> t1 -> t2 -> t3) -> t) -> t) gamma0<br />
> --}<br />
<br />
Other terms to try:<br />
((((.) . (.)) . (.)) . (.))<br />
((flip .) . (((flip .) .) . (((.) . (.)) . (((.) . (.)) .))))<br />
reify const gamma0<br />
reify (.) gamma0<br />
reify (asTypeOf __ (.)) gamma0<br />
<br />
> term1B = reify (undefined:: t4 -> (t3 -> t4 -> t5 -> t1) -> t6 -> t3 -><br />
> (t4 -> t -> t -> t5 -> t1 -> t2) -> t -> t5 -> t2) gamma0<br />
<br />
The type a->b however is not inhabitable: If we uncomment the following,<br />
<br />
> --test_not_derivable = reify (__::a -> b) gamma0<br />
<br />
we get the type error:<br />
No instances for (Resolve (Gamma (:*: (T2T (:*: a HNil)) HNil)) assum',<br />
HLookup rt HNil (:*: rt assum))<br />
arising from use of `reify' at ...<br />
<br />
That is, a |- rt is unprovable.<br />
<br />
* Code<br />
<br />
** Preliminaries<br />
<br />
An abbreviated notation for undefined, which shall occur very often<br />
<br />
> __ = __<br />
<br />
Heterogeneous lists<br />
<br />
> data HTrue<br />
> data HFalse<br />
> instance Show HTrue where show _ = "HTrue"<br />
> instance Show HFalse where show _ = "HFalse"<br />
<br />
> data HNil = HNil deriving Show<br />
> data HCons a b = HCons a b deriving Show<br />
<br />
> -- Syntax sugar from the HList library. Thanks to Ralf Laemmel<br />
> infixr 2 :*:<br />
> infixr 2 .*.<br />
> type e :*: l = HCons e l<br />
> a .*. b = HCons a b<br />
<br />
Environment: hs are hypotheses: an HList of T2T, each of which states one<br />
assumption: an association of a type to a term<br />
<br />
> data Gamma hs = G hs Int deriving Show<br />
> newtype T2T t = T2T Term deriving Show<br />
<br />
Converting an implication to a type list of assumptions in inverse order<br />
<br />
> class I2L t tl | t -> tl where<br />
> i2l :: t -> tl<br />
> i2l = undefined -- it's a type-level function<br />
><br />
> instance (IsFunction t flag, I2L' flag t tl)<br />
> => I2L t tl<br />
><br />
> class I2L' flag t tl | flag t -> tl<br />
><br />
> instance I2L' HFalse t (t :*: HNil)<br />
><br />
> instance (I2L x tlx, I2L y tly, HAppend tly (tlx :*: HNil) tl)<br />
> => I2L' HTrue (x->y) tl<br />
><br />
> ti1 = i2l (__::a->b->c)<br />
> ti2 = i2l (__::(a->b)->a->b)<br />
> ti3 = i2l (__::(a -> b -> c) -> (a -> b) -> a -> c)<br />
<br />
<br />
The main reification class<br />
<br />
> class Reify t gamma where<br />
> reify :: t -> gamma -> Term<br />
><br />
> instance (IsFunction t flag, I2L' flag t (rt :*: at),<br />
> AddHyp gamma at gamma',<br />
> Resolve gamma' ((rt :*: HNil) :*: HNil))<br />
> => Reify t gamma where<br />
> reify t gamma = let (varlist, gamma') = add'hyp gamma (__::at) []<br />
> in foldr (\ (Var v) s -> L v s )<br />
> (resolve gamma' (((__::rt) .*. HNil) .*. HNil) [])<br />
> varlist<br />
<br />
Label top-level assumptions with variables<br />
<br />
> class AddHyp gamma tl gamma' | gamma tl -> gamma' where<br />
> add'hyp :: gamma -> tl -> [Term] -> ([Term],gamma')<br />
><br />
> instance AddHyp gamma HNil gamma where<br />
> add'hyp g _ varlist = (varlist,g)<br />
><br />
> instance AddHyp (Gamma ((T2T t) :*: hs)) r gamma<br />
> => AddHyp (Gamma hs) (t :*: r) gamma where<br />
> add'hyp (G hs varcount) _ varlist =<br />
> let v = (Var varcount)<br />
> hs' = ((T2T v)::T2T t) .*. hs<br />
> in add'hyp (G hs' (varcount + 1)) (__::r) (v:varlist)<br />
<br />
<br />
** The SLD resolution algorithm<br />
<br />
> class Resolve gamma goals where<br />
> resolve :: gamma -> goals -> [Term] -> Term<br />
><br />
> instance Resolve gamma HNil where<br />
> resolve _ _ pt = foldr1 (flip A) pt<br />
><br />
> instance (HLookup g hs (g :*: assum),<br />
> HReverse assum assum',<br />
> Resolve (Gamma hs) assum',<br />
> Resolve (Gamma hs) gr)<br />
> => Resolve (Gamma hs) ((g :*: HNil) :*: gr) where<br />
> resolve gamma@(G hs _) _ pt =<br />
> let T2T t1 = hlookup (__::g) hs<br />
> in resolve gamma (__::gr) ((resolve gamma (__::assum') [t1]) : pt)<br />
><br />
> instance (AddHyp (Gamma hs) (gc :*: gcr) gamma',<br />
> AddHyp (Gamma ((T2T gc) :*: hs)) gcr gamma',<br />
> Resolve gamma' ((g :*: HNil) :*: HNil),<br />
> Resolve (Gamma hs) gr)<br />
> => Resolve (Gamma hs) ((g :*: gc :*: gcr) :*: gr) where<br />
> resolve gamma@(G hs _) _ pt =<br />
> let t1 = let (varlist, gamma'::gamma') =<br />
> add'hyp gamma (__::(gc :*: gcr)) []<br />
> in foldr (\ (Var v) s -> L v s )<br />
> (resolve gamma' (((__::g) .*. HNil) .*. HNil) [])<br />
> varlist<br />
> in resolve gamma (__::gr) (t1 : pt)<br />
<br />
Lookup in the `associative' type-indexed list<br />
<br />
> class HLookup t l w | t l -> w where<br />
> hlookup :: t -> l -> T2T w<br />
><br />
> instance (TypeEq t t' flag, HLookup' flag t ((T2T (t' :*: at)) :*: r) w)<br />
> => HLookup t ((T2T (t' :*: at)) :*: r) w where<br />
> hlookup = hlookup' (undefined::flag)<br />
><br />
> class HLookup' flag t l rt | flag t l -> rt where<br />
> hlookup' :: flag -> t -> l -> T2T rt<br />
><br />
> instance HLookup' HTrue t ((T2T (t :*: at)) :*: r) (t :*: at) where<br />
> hlookup' _ _ (HCons t _) = t<br />
><br />
> instance HLookup t r w => HLookup' HFalse t ((T2T t') :*: r) w where<br />
> hlookup' _ t (HCons _ r) = hlookup t r<br />
<br />
<br />
<br />
> class HAppend l1 l2 l | l1 l2 -> l where<br />
> happend :: l1 -> l2 -> l<br />
> instance HAppend HNil l2 l2 where<br />
> happend _ l2 = l2<br />
> instance HAppend l1 l2 l => HAppend (a :*: l1) l2 (a :*: l) where<br />
> happend (HCons a l1) l2 = a .*. (happend l1 l2)<br />
<br />
> class HReverse l1 l2 | l1 -> l2<br />
> instance HReverse HNil HNil<br />
> instance (HReverse l1 l1', HAppend l1' (a :*: HNil) l2)<br />
> => HReverse (a :*: l1) l2<br />
<br />
<br />
** Show Terms in a nice way<br />
<br />
> instance Show Term where<br />
> show (Var i) =<br />
> case divMod i 26 of<br />
> (0,i) -> simple_var i<br />
> (j,i) -> simple_var i ++ (show j)<br />
> where simple_var i = ["yphdcbaeijklmnofqrstuvwxgz" !! i]<br />
> show (A e v@(Var i)) = show e ++ " " ++ show v<br />
> show (A e1 e2) = show e1 ++ " " ++ "(" ++ show e2 ++ ")"<br />
> show (L i e) = show' [i] e<br />
> where show' vars (L j e) = show' (j:vars) e<br />
> show' vars e = "\\" ++ unwords (map (show.Var) $ reverse vars) ++<br />
> " -> " ++ show e<br />
<br />
<br />
* The second reifier: from types to bona fide Haskell terms<br />
<br />
The second reifier is a `lifted' version of the first one. Wherever we<br />
used regular Haskell lists before, we use HLists now.<br />
<br />
> newtype T2TT tl t = T2TT t deriving Show<br />
><br />
> class RR t gamma where<br />
> rr :: t -> gamma -> t<br />
><br />
> instance (IsFunction t flag, RR' flag t gamma)<br />
> => RR t gamma where<br />
> rr = rr' (__::flag)<br />
><br />
> class RR' flag t gamma where<br />
> rr' :: flag -> t -> gamma -> t<br />
><br />
> instance (IsFunction x flagx, I2L' flagx x tlx,<br />
> IsFunction y flagy, RR' flagy y ((T2TT tlx x) :*: gamma))<br />
> => RR' HTrue (x->y) gamma where<br />
> rr' _ _ gamma = \ (v::x) -> rr' (__::flagy) (__::y)<br />
> (((T2TT v)::T2TT tlx x) .*. gamma)<br />
><br />
> instance (RResolve gamma ((t :*: HNil) :*: HNil) HNil t)<br />
> => RR' HFalse t gamma where<br />
> rr' _ _ gamma = rresolve gamma (((__::t) .*. HNil) .*. HNil) HNil<br />
><br />
><br />
> class RResolve gamma goals tl t | gamma goals tl -> t where<br />
> rresolve :: gamma -> goals -> tl -> t<br />
><br />
> instance RResolve gamma HNil (t :*: HNil) t where<br />
> rresolve _ _ (HCons t HNil) = t -- foldr1 (flip A) pt<br />
><br />
> instance RResolve gamma HNil (t1 :*: tr) (t->r)<br />
> => RResolve gamma HNil (t :*: t1 :*: tr) r where<br />
> rresolve g _ (HCons t r) = (rresolve g HNil r) t<br />
><br />
> instance (RHLookup g gamma (T2TT (g :*: assum) g'),<br />
> HReverse assum assum',<br />
> RResolve gamma assum' (g' :*: HNil) ra,<br />
> RResolve gamma gr (ra :*: pt) t)<br />
> => RResolve gamma ((g :*: HNil) :*: gr) pt t where<br />
> rresolve gamma _ pt =<br />
> let T2TT t1 = rhlookup (__::g) gamma<br />
> ra :: ra = rresolve gamma (__::assum') (t1 .*. HNil)<br />
> in rresolve gamma (__::gr) (ra .*. pt)<br />
> -- the instance for improper combinators is left as an exercise to the reader<br />
<br />
> -- Lookup in the `associative' type-indexed list<br />
> class RHLookup t l w | t l -> w where<br />
> rhlookup :: t -> l -> w<br />
><br />
> instance (TypeEq t t' flag,RHLookup' flag t ((T2TT (t' :*: at) tt') :*: r) w)<br />
> => RHLookup t ((T2TT (t' :*: at) tt') :*: r) w where<br />
> rhlookup = rhlookup' (__::flag)<br />
><br />
> class RHLookup' flag t l w | flag t l -> w where<br />
> rhlookup' :: flag -> t -> l -> w<br />
><br />
> instance RHLookup' HTrue t ((T2TT (t :*: at) tt) :*: r)<br />
> (T2TT (t :*: at) tt) where<br />
> rhlookup' _ _ (HCons t _) = t<br />
><br />
> instance RHLookup t r w => RHLookup' HFalse t ((T2TT tl' t') :*: r) w where<br />
> rhlookup' _ t (HCons _ r) = rhlookup t r<br />
<br />
<br />
A few tests:<br />
<br />
> rtest1 = let f (x::a) (y::b) ::a = rr undefined HNil x y<br />
> in f 1 2<br />
> rtest2 = let f x y = rr (undefined::a->b->b) HNil x y<br />
> in f 1 2<br />
><br />
> -- \f x y -> f x :: forall t t1 t2. (t -> t1) -> t -> t2 -> t1<br />
> rtest3 = let t f x y = rr (undefined::(t -> t1) -> t -> t2 -> t1) HNil f x y<br />
> in t Just 1 'c'<br />
><br />
> rtest4 f g = rr (undefined::(b -> c) -> (a -> b) -> a -> c) HNil f g<br />
> -- *HC> rtest4 (:[]) (\x -> (True,x)) 10<br />
> -- [(True,10)]<br />
> -- must be truly polymorphic!<br />
<br />
<br />
* Equality and deconstruction of type schemas<br />
<br />
> class IsFunction a b | a -> b<br />
> instance TypeCast f HTrue => IsFunction (x->y) f<br />
> instance TypeCast f HFalse => IsFunction a f<br />
><br />
> -- literally lifted from the HList library<br />
> class TypeCast a b | a -> b, b->a where typeCast :: a -> b<br />
> class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b<br />
> class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b<br />
> instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x<br />
> instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast''<br />
> instance TypeCast'' () a a where typeCast'' _ x = x<br />
><br />
> class TypeEq' () x y b => TypeEq x y b | x y -> b<br />
> where type'eq :: x -> y -> b<br />
> type'eq _ _ = undefined::b<br />
> class TypeEq' q x y b | q x y -> b<br />
> class TypeEq'' q x y b | q x y -> b<br />
> instance TypeEq' () x y b => TypeEq x y b<br />
> instance TypeCast b HTrue => TypeEq' () x x b<br />
> instance TypeEq'' q x y b => TypeEq' q x y b<br />
> instance TypeEq'' () x y HFalse<br />
<br />
</pre><br />
<br />
[[Category:Idioms]]</div>Gwernhttps://wiki.haskell.org/index.php?title=From_a_newbie_II&diff=63933From a newbie II2021-02-06T15:19:41Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Beroal</p>
<hr />
<div>[[Category:Rants and comments]]<br />
== Introduction ==<br />
<br />
Hello there. I am another Haskell beginner. I am writting this page to tell my experience with Haskell so far, inspired by the article [[From a newbie]].<br />
<br />
== First impressions of Haskell ==<br />
<br />
My first language was PHP, then C, then C++ and some ruby/python scattered sparsely. Then someone in the #c++ channel in Quakenet said something about Haskell and functional programming. He said there were 'no variables' or something of the sort, and how it had influenced and improved his C++ style. Since he was a pretty good programmer I decided to take a look. Ugh, what the f*ck is this? So it never went past taking a glance from the examples in wikipedia or haskell.org, learning by guessing and then giving up.<br />
<br />
Only 6 months after, out of sheer boredom I decided to resume my Haskell lessons. Naturally, I am enjoying it more than ever, since this 'feeling' that learning something \this\ new gives I had only found when learning C, or learning about OOP in ruby or C++.<br />
<br />
== Learning Haskell takes lots of time and practice ==<br />
<br />
Just like it took... what, 2 years? to learn C++ (and I still don't consider myself good at it), I think Haskell has a loooong learning curve. Specially if you come from an imperative background.<br />
:That is the problem. Imperative or OOP entrenches in your brain and repels other paradigms. Just learn Haskell earlier. --[[User:Beroal|Beroal]] 05:13, 20 January 2010 (UTC)<br />
<br />
== Learning Haskell made easy (easier) ==<br />
<br />
Short and sweet:<br />
* Print the haskell98 report - read.<br />
* #haskell on freenode - ask.<br />
<br />
== Haskell can be interpreted AND compiled? ==<br />
<br />
I have to admit this was one of the features about it that attracted me the most. So far I had dealt with either compiled languages (C, C++) or interpreted (Ruby, Python, PHP). This just looked awesome. And it is.<br />
<br />
== Haskell can be used to write real-world stuff ==<br />
<br />
Amazing, so it's not educational oriented only, but rather has a rather large standard library for interfacing with the real-world (WIN32 Api, OpenGl, Networking, etc). Sweet.<br />
<br />
== Elegant solutions here I come ==<br />
I'm not even sure if I like the code more than the resulting binaries sometimes. :)<br />
<br />
== Wtfux is a monad ==<br />
I think I'm getting it...amazing. Start by understanding IO. Then realize what a monad IS. Then make your own monads. Oh my gosh.</div>Gwernhttps://wiki.haskell.org/index.php?title=GHC/Common_Error_Messages&diff=63932GHC/Common Error Messages2021-02-06T15:19:40Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by MichalPalka</p>
<hr />
<div>This page is meant to explain typical causes of some error messages generated by the [[GHC]] during compilation and runtime. The page should explain basic errors in terms understandable for real newbies.<br />
<br />
== Compile errors ==<br />
<br />
=== Type errors ===<br />
''Remark that [[GHC]]'s type errors are not always in the right places should go here''<br />
<br />
==== Couldn't match type ====<br />
<br />
==== Infinite type ====<br />
<br />
=== Parse errors ===<br />
<br />
=== Other errors ===<br />
<br />
== Runtime errors ==</div>Gwernhttps://wiki.haskell.org/index.php?title=Cabal/NewBuild&diff=63931Cabal/NewBuild2021-02-06T15:19:39Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Hvr</p>
<hr />
<div><br />
This page provides information about <code>cabal new-build</code>, the main entry point into Cabal's new Nix-style local builds facility.<br />
<br />
== Official documentation ==<br />
<br />
The latest official documentation can be found in the Cabal User Guide, in chapter [http://cabal.readthedocs.io/en/latest/nix-local-build-overview.html 5. Nix-style Local Builds].<br />
<br />
== Additional Resources ==<br />
<br />
* Haskell at Work's [https://haskell-at-work.com/episodes/2018-05-13-introduction-to-cabal.html "Introduction to Cabal" screencast] includes an introduction to basic use of some of the <code>new-*</code> commands.</div>Gwernhttps://wiki.haskell.org/index.php?title=A_new_list_type&diff=63930A new list type2021-02-06T15:19:38Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by MathematicalOrchid</p>
<hr />
<div>Does anybody find this amusing?<br />
<br />
<haskell><br />
module XList where<br />
<br />
import Prelude hiding (length, head, tail, foldr, foldl, map, zip, zipWith, replicate)<br />
<br />
data List t = Node {length_ :: Int, head :: t, tail :: List t} | End deriving (Eq, Show)<br />
<br />
length End = 0<br />
length n = length_ n<br />
<br />
infixr 5 #:<br />
<br />
x #: xs = Node (1 + length xs) x xs<br />
<br />
foldr _ v (End) = v<br />
foldr f v (Node _ x xs) = f x (foldr f v xs)<br />
<br />
foldl _ v (End) = v<br />
foldl f v (Node _ x xs) = foldl f (v `f` x) xs<br />
<br />
foldl' _ v (End) = v<br />
foldl' f v (Node _ x xs) = (foldl' f $! v `f` x) xs<br />
<br />
map _ (End) = End<br />
map f (Node n x xs) = Node n (f x) (map f xs)<br />
<br />
zipWith f (End) _ = End<br />
zipWith f _ (End) = End<br />
zipWith f (Node n0 x xs) (Node n1 y ys) = Node (n0 `min` n1) (f x y) (zipWith f xs ys)<br />
<br />
zip = zipWith (\x y -> (x,y))<br />
<br />
join (End) ys = ys<br />
join (Node n x xs) ys = Node (n + length ys) x (join xs ys)<br />
<br />
merge = foldr join End<br />
<br />
select _ End = End<br />
select f (Node n x xs) = case f x of<br />
True -> x #: select f xs<br />
False -> select f xs<br />
<br />
replicate 0 _ = End<br />
replicate n x = Node n x (replicate (n-1) x)<br />
</haskell><br />
<br />
Somebody (a non Haskeller) said that having to traverse a potentially large linked list merely to compute its size is unnecessarily wasteful. Whether or not you agree with that statement, the above (which is obviously incomplete) is what I came up with to address this criticism. (You might argue that linked lists just plain aren't a good idea for very large structures.)<br />
<br />
Of course, in the presence of lazy evaluation, all is not ''quite'' that simple. Functions that generate known-size lists (e.g., <hask>replicate</hask>) can add size information as they build it. If <hask>map</hask> is applied to a list who's size is known, the size of the result is known. (Interestingly, if it isn't known, then presumably asking for the size of the result also computes and stores the size of the source list - if anybody still has it.) The really interesting case is <hask>select</hask> (which is equivalent to <hask>Prelude.filter</hask>, but with a less brain-dead name).<br />
<br />
Anybody else have any insightful or amusing comments?<br />
<br />
[[User:MathematicalOrchid|MathematicalOrchid]] 13:28, 14 February 2007 (UTC)<br />
<br />
"''traversing a potentially large linked list merely to compute its size is unnecessarily wasteful.''"<br />
Especially when it's infinite. See [[Things to avoid]] for why you should try to avoid calling <hask>length</hask>. Although it probably requires quite a change of mindset for a non-Haskeller to appreciate that.<br />
<br />
[[User:Remi|Remi]]<br />
<br />
Agreed; trying to count the elements in an infinite list would be a Bad Idea. ;-)<br />
<br />
This came up in a discussion of sorting algorithms. You might want to choose which algorithm to apply depending on how big the list is - but not much point doing that if it takes longer to figure out how big the list is then to just use the first algorithm to hand! (Note that a sorting algorithm can ''never'' work on an infinite list.)<br />
<br />
For the special case of a sorting algorithm, it might be simpler to just count the size of the list once, and then manually manage that information throughout the sorting process. (Rather than, as above, defining a whole new datatype and redefining all of the prelude on it.)<br />
<br />
I thought I would post it because it's an interesting idea though.<br />
<br />
[[User:MathematicalOrchid|MathematicalOrchid]] 15:32, 14 February 2007 (UTC)<br />
<br />
[[Category:Code]]</div>Gwernhttps://wiki.haskell.org/index.php?title=AmeroHaskell&diff=63929AmeroHaskell2021-02-06T15:19:37Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by EricSessoms</p>
<hr />
<div>AmeroHaskell, a Haskell get together for/in the SouthEastern USA.<br />
Now a Haskell get together(s) anywhere in the USA with at least one in Portland, OR.<br />
<br />
== Likely Attendees ==<br />
<br />
=== Western ===<br />
<br />
* [[User:Taral|Taral]] - Seattle, WA, will travel.<br />
* [[DonStewart]], in OR, but would travel for haskell<br />
* [[TimChevalier]] - Portland, OR. Might be willing to travel, depending on where and when.<br />
* [[User:CliffordBeshers|CliffordBeshers]] - San Diego, CA, but would consider travelling.<br />
* [[JohnMeacham]] - Pasadena, CA. might be able to travel depending on when. (would prefer somewhere on west coast)<br />
* [[GregFitzgerald]] - San Diego, CA<br />
* [[BryanOSullivan]] - San Francisco, CA, will travel.<br />
* [[Derek Elkins]], in TX, would travel some, probably would only stay for a day or two.<br />
* [http://www.travishartwell.net/blog/ Travis B. Hartwell] aka Nafai Willing to travel some, probably can't take any time off of work but most weekends are good except Nov. 2-4 and 16-18.<br />
* [[JustinBailey]] - Can't really travel, but in Portland, OR.<br />
* [[JohnDorsey]] - In Houston, TX. Slight chance of travel elsewhere.<br />
* [[MikeVanier]] - Pasadena, CA. Could travel depending on the date, prefer west coast.<br />
* [[GregHeartsfield]] - Dallas, TX. will travel (tentatively).<br />
<br />
=== Eastern ===<br />
<br />
* [[Rahul Kapoor]] - Providence, RI, will travel for Haskell.<br />
* [[AdamPeacock]] - NYC, will travel.<br />
* [http://byorgey.wordpress.com Brent Yorgey] (byorgey) - Washington, DC. <br />
* [[Bjorn Buckwalter]] - Washington, DC. Unlikely to travel.<br />
* [[Betty]] - Raleigh, NC<br />
* [[Dino]] Morelli - Raleigh, North Carolina. Will travel some, can stay somewhere overnight(s). Week of Oct 13-20 is not doable.<br />
* [[Peter Gavin]] - Tallahassee, FL, willing to drive a few hours; weekends are best<br />
* [[Bernard Putersznit]] - Ocala, FL, willing to drive a few hours; any day of the week. Available from November onward.<br />
* [[ShaeErisson]] - located in Boston, MA - pretty much any date is good for me.<br />
* Garrett Mitchener - Charleston, SC, probably can't come if I have to fly<br />
<br />
== Possible locations ==<br />
<br />
* Portland, OR<br />
* Credit Suisse, NY<br />
<br />
== Potential Presenters ==<br />
<br />
* [[Derek Elkins]] - I can provide a talk for categorical ideas that are directly applicable in Haskell (e.g. free monads, initial algebras, etc.) and/or something on using types to enforce invariants without going ''too'' crazy (e.g. wrapper types, phantom types, type class traits, reasonable examples of type level programming)<br />
* [[TimChevalier]] - if you're really hard up for speakers, I could scrape something up.<br />
<br />
== When ==<br />
<br />
* For a Portland meeting, probably in a January/February time-frame<br />
* Maybe during SIGCSE in Portland March 12-15<br />
<br />
[[Category:Events]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Anagrams&diff=63928Anagrams2021-02-06T15:19:36Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Ptolomy</p>
<hr />
<div><haskell><br />
module Main (main) where<br />
import System.Environment (getArgs)<br />
import Data.Char (toUpper,isAlpha)<br />
import Data.List (sortBy)<br />
import Data.Ord (comparing)<br />
import qualified Data.ByteString.Char8 as B<br />
<br />
data CharCount = CharCount !Char !Int deriving (Show, Eq)<br />
data WordData = WordData B.ByteString [CharCount] deriving (Show, Eq)<br />
<br />
main = do<br />
[n] <- getArgs<br />
wl <- B.readFile n <br />
user <- B.getLine <br />
let results = findAnagrams (makeWordList wl) (countChars user)<br />
B.putStr . B.unlines . map B.unwords $ results<br />
<br />
findAnagrams :: [WordData] -> [CharCount] -> [[B.ByteString]]<br />
findAnagrams [] _ = []<br />
findAnagrams lst@((WordData bs cc):rest) qcc =<br />
case (qcc `minus` cc) of<br />
Nothing -> remaining<br />
Just [] -> [bs]:remaining <br />
Just x -> map ((:) bs) (findAnagrams lst x) ++ remaining<br />
where remaining = findAnagrams rest qcc<br />
<br />
minus :: (Monad m) => [CharCount] -> [CharCount] -> m [CharCount]<br />
minus x [] = return x<br />
minus [] _ = fail "can't subtract from empty" <br />
minus (lft@(CharCount c1 i1):xs) r@((CharCount c2 i2):ys)<br />
| (c1 == c2) && (i2 == i1) = xs `minus` ys<br />
| (c1 == c2) && (i2 < i1) = do rem <- xs `minus` ys<br />
return $! (CharCount c1 (i1 - i2)):rem<br />
| (c1 < c2) = do rem <- xs `minus` r<br />
return $! lft:rem<br />
| (c1 == c2) && (i2 > i1) = fail "right has more chars than left" <br />
| (c1 > c2) = fail "right has chars not in left" <br />
| otherwise = error "Bad condition"<br />
<br />
countChars :: B.ByteString -> [CharCount] <br />
countChars = map counts . B.group . B.sort . B.map toUpper . B.filter isAlpha <br />
where counts x = CharCount (B.head x) (B.length x)<br />
<br />
makeWordList :: B.ByteString -> [WordData]<br />
makeWordList = map (\w -> WordData w (countChars w)) . sortBy (flip (comparing B.length)) . B.words<br />
<br />
</haskell><br />
<br />
[[Category:Code]]</div>Gwernhttps://wiki.haskell.org/index.php?title=BerkeleyDBXML&diff=63927BerkeleyDBXML2021-02-06T15:19:35Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Blackh</p>
<hr />
<div>== Introduction ==<br />
<br />
If you are using Berkeley DB, and not Berkeley DB XML, then please skip to the Berkeley DB section.<br />
<br />
Berkeley DB XML is a powerful, fully transactional, XML-based database that uses<br />
[http://www.w3.org/XML/Query/ XQuery] (a W3C standard) as its query language. (Berkeley DB XML does NOT use SQL.)<br />
<br />
This page is an introduction/tutorial on writing a multi-threaded Berkeley DB XML application in Haskell. It is intended for Haskell programmers who are new to Berkeley DB XML.<br />
<br />
I hope you will consider the advantages of using an XML database over the traditional SQL database in your application. However, note that ''Berkeley DB and DB XML are non-free for commercial use''.<br />
<br />
=== Obtaining and building the packages ===<br />
<br />
Downloads<br />
* [http://www.oracle.com/database/berkeley-db/xml/index.html Berkeley DB XML]<br />
* [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/BerkeleyDB Haskell binding for Berkeley DB]<br />
* [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/BerkeleyDBXML Haskell binding for Berkeley DB XML]<br />
<br />
Berkeley DB XML is easy to build. On Unix, the ./buildall.sh script will build everything<br />
for you, including Berkeley DB, and put the resulting image into the 'install'<br />
directory. You can then copy this directory's contents to an install location<br />
of your choice.<br />
<br />
On a GNU/Linux system, you may want to add the 'lib' directory of this install<br />
location under /etc/ld.so.conf.d/ then run "ldconfig". This will allow the system<br />
to find the Berkeley DB XML libraries. If you don't do this, you will have to<br />
set the environment variable LD_LIBRARY_PATH.<br />
<br />
If you are using a Unix system, your system may already have a sufficiently recent<br />
version of Berkeley DB. In this case, it is better to use this and build Berkeley<br />
DB XML only. The commands for this are as follows:<br />
<br />
<pre><br />
./buildall.sh --build-one=xerces<br />
./buildall.sh --build-one=xqilla<br />
./buildall.sh --build-one=dbxml --with-berkeleydb-prefix=/usr<br />
</pre><br />
<br />
To test your installation, see if you can run the 'dbxml' command from the install<br />
image's bin directory. This is an interactive utility that allows you to run<br />
database queries and view the results.<br />
<br />
The Berkeley DB XML binding for Haskell is a standard Cabal package. Its README<br />
file gives installation instructions.<br />
<br />
=== The binding ===<br />
<br />
This tutorial uses a Haskell binding for DB XML that sticks closely to Berkeley<br />
DB XML's C++ interface, so we are programming at a fairly low level.<br />
<br />
DB XML would lend itself to the development of higher-level wrappers. For<br />
example, someone could write a drop-in replacement for STM (Software<br />
Transactional Memory) that uses DBXML to give persistent storage.<br />
<br />
=== Adventure game example ===<br />
<br />
In the Berkeley DB XML binding distribution, you will find a tiny adventure game<br />
under examples/adventure/. This<br />
tutorial will refer to the code in this example.<br />
<br />
Note that this game is multi-user and the game world, including player locations,<br />
is stored persistently, so it survives a re-start of the adventure server.<br />
<br />
Here is an example session:<br />
<br />
<pre><br />
blackh@amentet:~/temp/BerkeleyDBXML-0.5/examples/adventure$ ./adventure<br />
Adventure server - please telnet into port 1888<br />
tidying up 0 cadavers<br />
Creating the game world...<br />
</pre><br />
<br />
<pre><br />
blackh@amentet:~$ telnet localhost 1888<br />
Trying 127.0.0.1...<br />
Connected to localhost.<br />
Escape character is '^]'.<br />
Welcome to 'DB/XML Haskell binding' adventure by Stephen Blackheath<br />
Please enter your name.<br />
> Stephen<br />
Welcome for the first time, Stephen.<br />
<br />
For help, please type "help".<br />
<br />
You are on a wide, white sandy beach. A bright blue ocean stretches to the<br />
horizon. Along the beach to the north you can see some large rocks. There is<br />
thick jungle to the west.<br />
You can see<br />
a starfish<br />
> get starfish<br />
You pick up a starfish.<br />
> west<br />
You are in a dense jungle.<br />
You can see<br />
a tall, twisty tree<br />
> drop starfish<br />
You drop a starfish.<br />
> look<br />
You are in a dense jungle.<br />
You can see<br />
a starfish<br />
a tall, twisty tree<br />
><br />
</pre><br />
<br />
== Berkeley DB ==<br />
<br />
DB XML is built on top of Berkeley DB. This section describes the concepts<br />
specific to DB.<br />
<br />
=== DB Environment ===<br />
<br />
Berkeley DB is not client-server like most SQL databases. It accesses its<br />
database files in a local directory.<br />
<br />
An "environment" is a directory with various odd-looking files such as<br />
__db.001 and log.0000000001, as well as various database files that your<br />
application has created. An application would normally have only one<br />
environment, where it would store all its databases. Database transactions<br />
operate within an environment, so a single transaction can span multiple<br />
database files in the same environment. This also means that you can update<br />
both Berkeley DB files and Berkeley DB XML files in a single transaction.<br />
<br />
When DB_THREAD is enabled, the environment will work safely with multi-threaded<br />
applications, and also multiple processes accessing the databases at the same<br />
time. This means you can run the 'dbxml' command-line utility while your<br />
application is running.<br />
<br />
When the DB_INIT_LOG flag is enabled, the environment contains a transaction log that<br />
forms part of the databases. Do not delete these files, or you will<br />
corrupt your databases. Also when DB_INIT_LOG is enabled, you cannot move your database files<br />
from one environment to another. The recommended way to do this is to use Berkeley's<br />
dbxml_dump/dbxml_load for DB XML files and db_dump/db_load for DB files.<br />
<br />
It is safe, however, to delete databases you have created without deleting the<br />
environment. The environment will detect this and adjust accordingly. You can,<br />
of course, start with a clean slate by deleting all the environment files and<br />
databases.<br />
<br />
A production application must periodically call dbEnv_txn_checkpoint to clear old<br />
data from the log.* files. (The adventure game example does not do this.)<br />
<br />
Here is some example code which will open an existing environment, or create it<br />
if it doesn't exist. These are the flags to use for a transactional, multi-threaded<br />
application:<br />
<br />
<haskell><br />
dbenv <- dbEnv_create []<br />
<br />
-- Enable automatic deadlock detection.<br />
dbEnv_set_lk_detect dbenv DB_LOCK_DEFAULT<br />
<br />
dbEnv_open dbenv "." [DB_CREATE,DB_INIT_LOCK,DB_INIT_LOG,DB_INIT_MPOOL,<br />
DB_INIT_TXN,DB_THREAD,DB_RECOVER] 0<br />
</haskell><br />
<br />
=== Deadlock detection ===<br />
<br />
Berkeley DB will automatically detect deadlocks for you, allowing you to<br />
re-start the deadlocked transaction. Because of the way Berkeley DB has been engineered, deadlock detection is '''not optional''' in<br />
multi-threaded applications. It is absolutely impossible to avoid deadlocks by<br />
the traditional method of carefully controlling the order of locking, because Berkeley DB will lock whole pages, which means it will unpredictably lock more than you told it to.<br />
<br />
Your application needs one and only one lock detector thread or process running per environment.<br />
dbEnv_set_lk_detect is an easy way to spawn one such thread. See the Berkeley DB<br />
documentation for other ways.<br />
<br />
If your application has more than one process, you can't do it the way this example does it. You<br />
would need to manage things so only one lock detector was running.<br />
<br />
Because of deadlock detection, your code must detect deadlocks and re-start the<br />
transaction if they are found. Here is some code to do this:<br />
<br />
<haskell><br />
-- Execute the specified code within a database transaction, automatically<br />
-- re-trying if a deadlock is detected.<br />
inTransaction :: XmlManager -> (XmlTransaction -> IO a) -> IO a<br />
inTransaction mgr code = inTransaction_ mgr code 0<br />
where<br />
inTransaction_ mgr code retryCount = do<br />
trans <- xmlManager_createTransaction mgr []<br />
catch<br />
(do<br />
result <- code trans<br />
xmlTransaction_commit trans<br />
return result<br />
)<br />
(\exc -> do<br />
hPutStrLn stderr $ "EXCEPTION "++show exc<br />
xmlTransaction_abort trans<br />
case fromException exc of<br />
Just (DbException _ DB_LOCK_DEADLOCK) | retryCount < 20 -> do<br />
hPutStrLn stderr "<<retry deadlocked thread>>"<br />
inTransaction_ mgr code (retryCount+1)<br />
_ -> throwIO exc)<br />
</haskell><br />
<br />
Remember that the code above pre-supposes that you have started a deadlock detector. If this hasn't happened, the application will stall and never throw DB_LOCK_DEADLOCK.<br />
<br />
Because your transaction can be re-started, you should not do any normal I/O inside your transaction. It would be even better if (like in Software Transactional Memory) the transactional code runs in a monad of its own that prevents normal access to the IO monad.<br />
<br />
=== Environment recovery ===<br />
<br />
Before you start your application, you must run a database recovery to return<br />
the database to a consistent state, in case of a dirty shutdown. This can either<br />
be done with the db_recover command line utility, or by specifying the DB_RECOVER<br />
flag to dbEnv_open.<br />
<br />
An environment recovery must run without any other processes accessing the database environment.<br />
Therefore it must be performed before you start your application.<br />
<br />
Because we are using the DB_RECOVER flag to do our recovery, we could not run multiple processes of 'adventure'<br />
at the same time unmodified. If we wanted this application to work with<br />
multiple processes, both the DB_RECOVER flag and the dbEnv_set_lk_detect<br />
call would need to be removed and run separately before the application was<br />
started.<br />
<br />
== Berkeley DB XML ==<br />
<br />
All the important topics are covered in "Getting Started with<br />
Berkeley DB XML" guide that comes with the Berkeley DB XML distribution, so I will only cover more Haskell-specific things here.<br />
<br />
Berkeley DBXML returns its document contents as a strict ByteString containing XML text. You need to use an XML library of some kind to handle these. The Haskell binding leaves you free to choose your own XML library. (I am also the developer of the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hexpat hexpat] and [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hexpat-pickle hexpat-pickle] packages, so you might consider using them since I designed them to fit nicely with BerkeleyDBXML.)<br />
<br />
Please take a look at the source code of the adventure example included with the DB XML binding distribution. Here are some examples from it:<br />
<br />
=== Example 1: Querying documents ===<br />
<br />
Here is an example that covers a lot of ground: The "query" function from the adventure game:<br />
<br />
<haskell><br />
collectM :: Monad m => m (Maybe a) -> m [a]<br />
collectM valueM = do<br />
value <- valueM<br />
case value of<br />
Just item -> do<br />
rest <- collectM valueM<br />
return (item:rest)<br />
Nothing -> do<br />
return []<br />
<br />
query_ :: (XmlManager, XmlContainer, XmlTransaction) -> PU [UNode String] p<br />
-> String -> [(String, XmlValue)] -> [DbXmlFlag] -> IO [(XmlDocument, p)]<br />
query_ (mgr, cont, trans) pickler queryText params flags = do<br />
qctx <- xmlManager_createQueryContext mgr LiveValues Eager<br />
let collection = xmlContainer_getName cont<br />
xmlQueryContext_setDefaultCollection qctx collection<br />
forM params $ \(name, value) -> do<br />
xmlQueryContext_setVariableValue qctx name value<br />
res <- xmlManager_query mgr (Just trans) queryText qctx flags<br />
docs <- collectM (xmlResults_next res)<br />
records <- forM docs $ \doc -> do<br />
text <- xmlDocument_getContent doc<br />
value <- case unpickleXML' defaultParserOptions (xpRoot pickler) text of<br />
Left err -> fail $ "unpickle failed: "++err<br />
Right value -> return value<br />
return (doc, value)<br />
return records<br />
<br />
query :: XmlPickler [UNode String] p => (XmlManager, XmlContainer, XmlTransaction) -> PU [UNode String] p<br />
-> String -> [(String, XmlValue)] -> IO [p]<br />
query ctx pickler queryText params = liftM (map snd) $ query_ ctx pickler queryText params []<br />
</haskell><br />
<br />
The 'query' function is a helper that calls 'query_' and returns the results as Haskell data structures only, discarding the XmlDocument objects. (XmlDocuments are useful as a reference to a document for updating or deleting.)<br />
<br />
Now look at 'query_'. First, we create a query context. This holds the variable assignments used in the XQuery. For example, if we call 'query' like this...<br />
<br />
<haskell><br />
items <- query db xpItem "collection()/item[@location=$loc]"<br />
[("loc", xmlString loc)]<br />
</haskell><br />
<br />
...then we push "loc" and its value into the query context, so the XQuery parser can resolve the variable $loc. This query says "give me all documents with a top-level tag of <item> containing a 'location' attribute matching $loc".<br />
<br />
xmlQueryContext_setDefaultCollection allows the XQuery to refer our document container as just "collection()" rather than having to name it explicitly in the XQuery string.<br />
<br />
Then we run the query, and use a helper called 'collectM' to extract the results from the XmlResults object and return them as a list of XmlDocument objects.<br />
<br />
The last step is iterate over the returned documents, using hexpat-pickle's unpickle functionality to translate the XML document into Haskell data structures.<br />
<br />
=== Example 2: Updating a document ===<br />
<br />
<haskell><br />
-- | Query with write lock. Returned document allows the document to be updated<br />
-- without having to specify its document name.<br />
queryUpdate :: XmlPickler [UNode String] p => (XmlManager, XmlContainer, XmlTransaction) -> PU [UNode String] p<br />
-> String -> [(String, XmlValue)] -> IO [(XmlDocument, p)]<br />
queryUpdate ctx pickler queryText params = query_ ctx pickler queryText params [DB_FLAG DB_RMW]<br />
<br />
update :: forall p . XmlPickler [UNode String] p =><br />
(XmlManager, XmlContainer, XmlTransaction)<br />
-> XmlDocument<br />
-> p<br />
-> IO ()<br />
update (mgr, cont, trans) doc p = do<br />
xmlDocument_setContent doc (pickleXML' (xpRoot xpickle :: PU (UNode String) p) p)<br />
uctx <- xmlManager_createUpdateContext mgr<br />
xmlContainer_updateDocument cont (Just trans) doc uctx<br />
</haskell><br />
<br />
'queryUpdate' works like 'query' in the previous example, except that it sets the DB_RMW flag, which means you get a write (exclusive) lock instead of the default read (non-exclusive) lock. Using a write lock makes no difference to the semantics of the transaction: It is just as atomic if you use a read lock. But, write locks can reduce the probability of transaction re-starts due to deadlocks, and so they improve efficiency when updating.<br />
<br />
A caller would pass the XmlDocument returned by queryUpdate to 'update', along with a modified version of the Haskell data structure p.<br />
<br />
'update' then pickles p, and proceeds to stuff the resulting XML string into the XmlDocument that queryUpdate gave us, and then issues the update.<br />
<br />
=== Unicode ===<br />
<br />
UTF-8 encoding is used throughout to encode Unicode text.<br />
All String arguments and return values in the binding are in Unicode, except for XML text, which is returned as 8-bit characters in a String data type. Your XML library will convert this to Unicode for you.<br />
<br />
The function xmlValue_asString is a case where the caller has to make the<br />
right choice. xmlValue_asString converts an XmlValue to a Unicode Haskell<br />
String. This is appropriate if you are fetching the text contents of an XML<br />
tag, for instance.<br />
<br />
However, if you are fetching XML text, you will want to<br />
call xmlValue_asString8Bit. This leaves out the conversion from UTF-8 to<br />
Unicode, so you can let your XML library convert this to Unicode.<br />
<br />
== Conclusion ==<br />
<br />
I hope this gets you started writing DB XML applications. If you have<br />
any questions (so I can improve this page), or wish to report bugs in the Haskell<br />
binding, please contact me at [http://blacksapphire.com/antispam/ Stephen Blackheath's anti-spam page].<br />
<br />
--[[User:Blackh|Blackh]] 10:28, 1 October 2008 (UTC)</div>Gwernhttps://wiki.haskell.org/index.php?title=Bounds_checking&diff=63925Bounds checking2021-02-06T15:19:34Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by DonStewart</p>
<hr />
<div>"There is a view that in order to gain static assurances such as an array index<br />
being always in range or tail being applied to a non-empty list, we must give<br />
up on something significant: on data structures such as arrays (to be replaced<br />
with nested tuples), on general recursion, on annotation-free programming, on<br />
clarity of code, on well-supported programming languages. <br />
<br />
That does not have to be the case. [These exampels] show non-trivial<br />
examples involving native Haskell arrays, index computations, and general<br />
recursion. All arrays indexing operations are statically guaranteed to be safe<br />
-- and so we can safely use an efficient unsafeAt provided by GHC seemingly for<br />
that purpose. The code is efficient; the static assurances cost us no run-time<br />
overhead. The example uses only Haskell98 + higher-ranked types. No new type<br />
classes are introduced. The safety is based on: Haskell type system, quantified<br />
type variables, and a compact general-purpose trusted kernel."<br />
<br />
[http://okmij.org/ftp/Haskell/types.html#branding Eliminating Array Bound Checking through Non-dependent types]<br />
<br />
[[Category:Idioms]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Bad_type_errors&diff=63926Bad type errors2021-02-06T15:19:34Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by BMeph</p>
<hr />
<div>Every now and again, GHC tells you that your program doesn't make sense. Unfortunately, the description it provides for the problem '''''also''''' does not make sense.<br />
Here is a list of some of the "worst offenders.<br />
----</div>Gwernhttps://wiki.haskell.org/index.php?title=Blueprint&diff=63924Blueprint2021-02-06T15:19:33Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Lemming</p>
<hr />
<div>The goal of the blueprint technique is to allow reading a data structure like <hask>Data.Map</hask> while constructing it.<br />
The idea is to separate the structure from the contained data.<br />
It is discussed at length in<br />
* Haskell-Cafe on [http://haskell.org/pipermail/haskell-cafe/2006-September/018133.html Optimization problem].<br />
<br />
[[Category:Idioms]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Bowling&diff=63923Bowling2021-02-06T15:19:32Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Newacct</p>
<hr />
<div>__TOC__<br />
<br />
== The problem ==<br />
<br />
Convert a list of number of pins knocked over by each ball into a final score for a game of ten pin bowling.<br />
<br />
== Solution by Eric Kidd == <br />
<br />
[http://www.randomhacks.net/articles/2007/04/28/bowling-in-haskell On his blog]. This is a recursive solution.<br />
<br />
== Short Solution by Chris Kuklewicz ==<br />
<br />
<haskell><br />
import Control.Monad.State<br />
<br />
score = sum . evalState (replicateM 10 (State scoreFrame))<br />
where scoreFrame (10:rest@(a:b:_)) = (10+a+b,rest)<br />
scoreFrame (x:y:rest) | x+y < 10 = (x+y,rest)<br />
| otherwise = (10+head rest,rest)<br />
<br />
score2 = fst . (!!10) . iterate addFrame . (,) 0<br />
where addFrame (total,10:rest@(a:b:_)) = (total+10+a+b ,rest)<br />
addFrame (total,x:y:rest) | x+y < 10 = (total+x+y ,rest)<br />
| otherwise = (total+x+y+head rest,rest)<br />
</haskell><br />
<br />
== Solution by Chris Kuklewicz ==<br />
<br />
Listed here. This has a monad-using parser with inferred type:<br />
<haskell>StateT [Int] (Error String) Frame</haskell><br />
The constraint that there are 10 frames is declared by using (replicateM 10). All invalid input lists should be recognized.<br />
<br />
<haskell><br />
module Bowling(Frame(..),Game(..),toGame,toBalls,score) where<br />
<br />
import Control.Monad(replicateM,when)<br />
import Control.Monad.State(get,put,evalStateT,StateT(..))<br />
import Control.Monad.Error(throwError)<br />
import Data.Array.IArray(Array,(!),elems,listArray,inRange)<br />
<br />
-- | Representation of a finished Game of bowling<br />
data Game = Game { gameScore :: Int<br />
, tenFrames :: Array Int Frame }<br />
deriving (Show,Eq)<br />
<br />
-- | Compact representation of a Frame from a finished Game<br />
data Frame = Normal { frameScore, first, second :: Int}<br />
| Spare { frameScore, first :: Int}<br />
| Strike { frameScore, next :: Int}<br />
deriving (Show,Eq)<br />
<br />
-- | Convert a list of pins to a final score<br />
score :: [Int] -> Int<br />
score balls = case toGame balls of<br />
Left msg -> error msg<br />
Right g -> gameScore g<br />
<br />
-- | Convert a Game to a list of (list of pins) for each frame<br />
toBalls :: Game -> [[Int]]<br />
toBalls (Game {tenFrames = frames}) = map decode (elems frames) ++ final<br />
where decode (Normal {first=x,second=y}) = [x,y]<br />
decode (Spare {first=x}) = [x,10-x]<br />
decode (Strike {}) = [10]<br />
final = case (frames ! 10) of<br />
Normal {} -> []<br />
Spare {frameScore=s} -> [[s-10]]<br />
Strike {frameScore=s,next=10} -> [[10],[s-20]]<br />
Strike {frameScore=s,next=a} -> [[a,s-a-10]]<br />
<br />
-- | Try to convert a list of pins to a Game<br />
toGame :: [Int] -> Either String Game<br />
toGame balls = do<br />
frames <- parseFrames balls<br />
return $ Game { gameScore = sum (map frameScore frames)<br />
, tenFrames = listArray (1,10) frames<br />
}<br />
<br />
-- This will only return an error or a list of precisely 10 frames<br />
parseFrames balls = flip evalStateT balls $ do<br />
frames <- replicateM 10 (StateT parseFrame)<br />
remaining <- get<br />
case (last frames,remaining) of<br />
(Normal {} , []) -> return frames<br />
(Spare {} , _:[]) -> return frames<br />
(Strike {} , _:_:[]) -> return frames<br />
_ -> err balls "Too many balls"<br />
<br />
parseFrame balls@(10:rest) = do<br />
case rest of<br />
(a:b:_) -> do<br />
checkBalls [a,b]<br />
when ((a /= 10) && (a+b > 10)) $<br />
err balls "More than 10 pins in frame after a strike"<br />
return (Strike (10+a+b) a,rest)<br />
_ -> err balls "Too few balls after a strike"<br />
<br />
parseFrame balls@(x:y:rest) = do<br />
checkBalls [x,y]<br />
case compare (x+y) 10 of<br />
GT -> err balls "More than 10 pins in a frame"<br />
LT -> return (Normal (x+y) x y,rest)<br />
EQ -> case rest of<br />
[] -> err balls "No ball after a spare"<br />
(a:_) -> do checkBall a<br />
return (Spare (10+a) x,rest)<br />
<br />
parseFrame balls = err balls "Not enough balls"<br />
<br />
err balls s = throwError (s ++ " : " ++ show (take 23 balls))<br />
checkBalls = mapM_ checkBall<br />
checkBall x = when (not (inRange (0,10) x))<br />
(throwError $ "Number of pins is of out range (0,10) : " ++ show x)<br />
</haskell><br />
<br />
[[Category:Code]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Meta%E3%83%81%E3%83%A5%E3%83%BC%E3%83%88%E3%83%AA%E3%82%A2%E3%83%AB&diff=63922Metaチュートリアル2021-02-06T15:19:30Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Ymotongpoo</p>
<hr />
<div>:''what i would like is a meta-tutorial''<br />
:''a list of questions about haskell, what does this do, do you understand this etc''<br />
: ''and if you say no, it points you at a tutorial which explains it'' -- ndm on #haskell<br />
<br />
一つのサイズの服があらゆる人にフィットするわけではありません！Metaチュートリアルでは '''あなたが''' 必要とするHaskellチュートリアルを探す手助けをします。私たちの説明の仕方がもしかするとあなたのレベルに対して"簡単すぎる"かもしれません。しかしとても簡潔にそして説明に不足なく書かれているので一度は目を通す価値があると思います。<br />
<br />
== Haskell 全般 ==<br />
<br />
=== とにかく早く始めたい人向け ===<br />
<br />
* [[Haskell入門 5ステップ]]<br />
* [[10分で学ぶHaskell]]<br />
<br />
=== プログラミング初心者向け ===<br />
<br />
* [http://en.wikibooks.org/wiki/Haskell The Haskell wikibook]<br />
* [http://en.wikibooks.org/wiki/Haskell/YAHT Yet Another Haskell Tutorial]<br />
<br />
=== プログラミング中級者向け ===<br />
<br />
# 関数型プログラミング初心者<br />
#* [http://www.haskell.org/~pairwise/intro/intro.html Haskell for C Programmers] - HaskellがあなたのC言語的な考え方を冒すって？このチュートリアルを試してみてください。<br />
#* [[Tutorials/Programming Haskell|Programming Haskell]] - [[User:DonStewart| dons]] が役立つプログラムの書き方や並列化での遊び方を最初から教えてくれます。<br />
#* [[Hitchhikers guide to Haskell]] - チュートリアルの進み方がゆっくりだったり、退屈だったり、意味不明になるのにうんざりだって？ヒッチハイカーのガイドを試してみてください。<br />
#* [http://learnyouahaskell.com/ Learn You a Haskell for Great Good!] 美しく、イラストがたくさん入ったHaskellのチュートリアルです<br />
# 他の関数型プログラミング言語の経験がある方<br />
#* [[A brief introduction to Haskell]] - "A brief introduction to OCaml（日本語訳：OCaml概要）"という記事のHaskell版で、Haskellの要点をおさえた解説です<br />
#* [http://www.haskell.org/tutorial/ Gentle Introduction To Haskell, version 98] - '''Gentle （日本語訳：優しい）''' というのは主観的な感想だと思います。。。<br />
#* [http://en.wikibooks.org/wiki/Haskell/Write_Yourself_a_Scheme_in_48_Hours Write Yourself a Scheme in 48 Hours]<br />
# Haskellがどんなものかちょっと見てみたいだけの方<br />
#* [[Simple unix tools]]<br />
#* [http://cs.anu.edu.au/student/comp1100/haskell/tourofsyntax.html A Tour of the Haskell Syntax]<br />
#* [[How to read Haskell]]<br />
<br />
<br />
== モナド ==<br />
<br />
# Haskell初心者の方<br />
# Haskellの構文は気にならないれど、モナドが気持ち悪い方（たとえばdo記法）<br />
#* [http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You could have invented monads! (And Maybe you Already Have!)]<br />
# 演習から学ぶのがとっつきやすい方<br />
# メタファーやアナロジーから学ぶ方<br />
#* [http://en.wikibooks.org/wiki/Haskell/Understanding_monads Understanding monads]<br />
#* [http://www.haskell.org/haskellwiki/Monads_as_containers Monads as containers]<br />
# 簡単なモナドは分かるけど、ネストやdoトリックを使う必要がある方<br />
#* [http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.pdf Monad Transformers Step by Step]<br />
#* [http://sigfpe.blogspot.com/2006/05/grok-haskell-monad-transformers.html Grok Monad Transformers]<br />
# 実用的にモナドがどのように使われているか見たい方<br />
#* [http://en.wikibooks.org/wiki/Haskell/Practical_monads Practical monads]<br />
# 圏論を理解していて圏論のモナドとHaskellのモナドの関係を知りたい方<br />
#* [http://db.ewi.utwente.nl/Publications/PaperStore/db-utwente-0000003696.pdf The Haskell Programmer's Guide to the IO Monad]<br />
# モナドのチュートリアルを読んで、用例から基本的なモナド関数の概要を知りたい方<br />
#* [http://members.chello.nl/hjgtuyl/tourdemonad.html A tour of the Haskell Monad functions]<br />
<br />
== 実用的なサンプル ==<br />
<br />
# 実用的なアプリケーションやライブラリを書きたい方<br />
#* [[How to write a Haskell program]]<br />
# いろいろ説明にはうんざりだって？クックブックじゃだめかい？<br />
#* [[Cookbook]]<br />
# 特にIOの使い方を知りたい方<br />
#* [[IO入門編]] - ざっと見てみる<br />
#* [http://www.cse.unsw.edu.au/~dons/blog/2006/12/18#ph-3 Programming Haskell: argument handling] - コマンドライン引数も扱います<br />
# 簡単なネットワーククライアントを書きたい方<br />
#* [[Roll your own IRC bot]]<br />
# GUIを作りたい方<br />
#* [http://en.wikibooks.org/wiki/Haskell/GUI Introductory gui programming]<br />
#* [http://www.haskell.org/gtk2hs/documentation/#tutorials With gtk2hs]<br />
#* [http://wxhaskell.sourceforge.net/quickstart.html With wxHaskell]<br />
# コンパイラやインタープリタを書きたい方<br />
#* [http://www.cse.unsw.edu.au/~dons/blog/2006/12/11#interpreters-with-reader-monads Quick interpreters with the Reader monad]<br />
#* [http://www.defmacro.org/ramblings/lisp-in-haskell.html Writing A Lisp Interpreter In Haskell]<br />
#* [http://en.wikibooks.org/wiki/Haskell/Write_Yourself_a_Scheme_in_48_Hours Write Yourself a Scheme in 48 Hours]<br />
<br />
[[Category:Tutorials]]<br />
<br />
Languages: [[Meta-tutorial|en]]</div>Gwernhttps://wiki.haskell.org/index.php?title=Humor/irish_joke&diff=63921Humor/irish joke2021-02-06T15:19:29Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Android</p>
<hr />
<div>==How to keep an imperative programmer busy for hours ==<br />
<br />
tell them the syntax for swapping two variables in Haskell is:<br />
<br />
<haskell><br />
let a=b; b=a in <exp><br />
</haskell></div>Gwernhttps://wiki.haskell.org/index.php?title=Yhc/Options&diff=63919Yhc/Options2021-02-06T15:19:28Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Kevin Reid</p>
<hr />
<div>Command syntax:<br />
yhc [options] file<br />
<br />
file: Name of the source file to compile, i.e. main.hs<br />
options: a list of options<br />
--flag turn on an option<br />
--noflag turn off an option<br />
--flag value pass a value as the flag<br />
<br />
Path Options:<br />
-I --includes str Include directories<br />
-P --preludes str Prelude directories<br />
-d --dst str destination path for generated bytecode files (default=.)<br />
-i --hidst str destinated path for generated .hi file (default=.)<br />
-w --wrapdst str destination path for generated FFI wrapper (default=.)<br />
--hide hide object files (default=off)<br />
<br />
Generation Options:<br />
--hat compile with Hat debugging support (default=off)<br />
--dotnet Generate .NET IL code (default=off)<br />
-W --genwrapper generate FFI wrapper (default=off)<br />
--hi-suffix str change the default ".hi" suffix (default=hi)<br />
--exportall export all identifiers from a module, despite what the <br />
export list says (default=off)<br />
<br />
Action Flags:<br />
--viewcore str View Core file (.ycr)<br />
-c --compile Compile one file only (default=off)<br />
<br />
Compilation Options:<br />
--redefine Don't complain if redefining an imported identifier <br />
(default=off)<br />
--unix Use unix file names (default=on)<br />
--unlit Unliterate the source code (default=off)<br />
--cpp Pre-process the file first (default=off)<br />
--prelude Keep prelude definitions in interface file (default=off)<br />
--lib Compiling a lib, don't complain if importing modules with <br />
names that differs from their filename. (default=off)<br />
--unifyhack Enable nasty type hack that's needed to make the prelude <br />
compile ... (default=off)<br />
<br />
Compliance Options:<br />
--underscore Enable H'98 underscore-is-lower-case (default=off)<br />
--puns Enable pre-98 named-field puns (default=on)<br />
--98 Haskell 98 compliance (default=off)<br />
<br />
Help Options:<br />
-v --version Show version information (default=off)<br />
-? --help Show all options and useage information (default=off)<br />
<br />
Core Options:<br />
--core generate a .ycr binary file (default=off)<br />
--showcore show the Core language (default=off)<br />
--linkcore generate a linked .yca binary file (default=off)<br />
<br />
Debug Options:<br />
--lex show lexical input (default=off)<br />
--parse show syntax tree after parser (default=off)<br />
--need show need table before import (default=off)<br />
--ineed show need table after import (default=off)<br />
--irename show rename table after import (default=off)<br />
--iineed show need table between all import files (default=off)<br />
--iirename show rename table between all imports (default=off)<br />
--rename show syntax tree after rename (default=off)<br />
--derive show syntax tree after derive (default=off)<br />
--remove show syntax tree after fields are removed (translated into <br />
selectors) (default=off)<br />
--scc show syntax tree after splitting into strongly connected <br />
groups (default=off)<br />
--type show syntax tree after type check (default=off)<br />
--fixsyntax show syntax tree after removing newtype constructors and <br />
fixing Class.Type.metod (default=off)<br />
--lift show syntax tree after lambda lifting (default=off)<br />
--case show stg tree after simplification of patterns <br />
(default=off)<br />
--prim show stg tree after inserting primitive functions <br />
(default=off)<br />
--bcodecompile show B code after compile (default=off)<br />
--bcodemem show B code after heap usage analysis (default=off)<br />
--bcodeflatten show B code after flattening (default=off)<br />
--bcoderel show B code after converting to relative jumps <br />
(default=off)<br />
--keepcase Don't lift case, we fix those later (default=off)<br />
--arity show stg tree after arity (default=off)<br />
--ibound show symbol table after import (default=off)<br />
--iibound show symbol table between all import files (default=off)<br />
--rbound show symbol table after rename (default=off)<br />
--dbound show symbol table after derive (default=off)<br />
--pbound show symbol table after inserting primitive functions <br />
(default=off)<br />
--ebound show symbol table after extract (default=off)<br />
--tbound show symbol table after type check (default=off)<br />
--fsbound show symbol table after adding Class.Type.method info <br />
(default=off)<br />
--lbound show symbol table after lambda lifting (default=off)<br />
--cbound show symbol table after simplification of pattern <br />
(default=off)<br />
--abound show symbol table after only atoms in applications <br />
(default=off)<br />
--import print name of imported files (default=off)<br />
--depend print imported identifiers that are used (not even alpha <br />
yet) (default=off)<br />
--free show stg tree with explicitly free variables (default=off)<br />
--atom show stg tree after only atoms in applications <br />
(default=off)<br />
--funnames insert position and name of functions in the code <br />
(default=off)<br />
--ilex show lexical input (default=off)<br />
--report-imports show only imports actually used (default=off)<br />
--showtype report type of "main" (default=off)<br />
--showwidth num set width for showing intermediate program (default=80)<br />
--showindent num set indentation for nesting (default=2)<br />
--showqualified show qualified ids as far as possible (default=on)<br />
<br />
<br />
<br />
Environment variables:<br />
<br />
YHC_BASE_PATH The path to the Yhc compiler base directory<br />
PATH The search path is used to find the compiler,<br />
if YHC_BASE_PATH is not specified</div>Gwernhttps://wiki.haskell.org/index.php?title=Ireland_HUG&diff=63920Ireland HUG2021-02-06T15:19:28Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Henk-Jan van Tuyl</p>
<hr />
<div>Announcements regarding the provisional (as of Jan. 2012) Ireland Haskell User's Group will be posted here.<br />
<br />
If you are interested in participating, please join the [https://groups.google.com/group/eire-hug/ mailing list].<br />
<br />
<br />
[[Category:Community]]</div>Gwernhttps://wiki.haskell.org/index.php?title=The_Monad.Reader/Discuss_Issue11/FingerTreeIMap&diff=63918The Monad.Reader/Discuss Issue11/FingerTreeIMap2021-02-06T15:19:26Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Dfplace</p>
<hr />
<div>--[[User:Dfplace|Dfplace]] 16:19, 12 September 2008 (UTC)<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-}<br />
module IMap where<br />
import Data.FingerTree <br />
import Data.List hiding (insert,delete,lookup)<br />
import Prelude hiding (lookup)<br />
import Data.Monoid<br />
<br />
data Elem a b = Elem a b <br />
<br />
data Key k v = NoKey | Key k v <br />
<br />
instance Eq k => Eq (Key k v) where <br />
(Key j _) == (Key k _) = j == k<br />
NoKey == NoKey = True<br />
NoKey == (Key _ _) = False<br />
(Key _ _) == NoKey = False<br />
<br />
instance Ord k => Ord (Key k v) where <br />
compare (Key j _) (Key k _) = compare j k<br />
compare NoKey NoKey = EQ<br />
compare (Key _ _) NoKey = GT<br />
compare NoKey (Key _ _ ) = LT<br />
<br />
instance Monoid v => Monoid (Key a v) where<br />
mempty = NoKey<br />
k `mappend` NoKey = k<br />
NoKey `mappend` k = k<br />
(Key _ x) `mappend` (Key k y) = Key k (x `mappend` y)<br />
<br />
data IMap a b = IMap (FingerTree (Key a b) (Elem a b))<br />
<br />
instance (Monoid b) => Measured (Key a b) (Elem a b) where<br />
measure (Elem x y) = Key x y<br />
<br />
insert :: (Ord k, Monoid v) => k -> v -> IMap k v -> IMap k v<br />
insert k v (IMap xs) = insert' $ viewl r<br />
where<br />
(l,r) = split (>= Key k undefined) xs<br />
new = IMap ( l >< (Elem k v <| r))<br />
insert' ((Elem y _) :< r') <br />
| k == y = IMap ( l >< (Elem k v <| r'))<br />
| otherwise = new<br />
insert' EmptyL = new<br />
<br />
delete :: (Ord k, Monoid v) => k -> IMap k v -> IMap k v<br />
delete x (IMap xs) = IMap (l >< r')<br />
where <br />
(l,r) = split (>= Key x undefined) xs<br />
(_,r') = split (> Key x undefined) r<br />
<br />
lookup :: (Monad m, Ord t, Monoid v) => t -> IMap t v -> m v<br />
lookup x (IMap xs) = lookup' $ <br />
viewl . snd $ <br />
split (>= Key x undefined) xs<br />
where <br />
lookup' ((Elem y v) :< _) <br />
| y == x = return v <br />
| otherwise = fail "IMap.lookup failed"<br />
lookup' EmptyL = fail "IMap.lookup failed"<br />
<br />
getValue :: (Monoid v) => IMap k v -> v<br />
getValue (IMap xs) = let (Key _ v) = measure xs in v<br />
</haskell></div>Gwernhttps://wiki.haskell.org/index.php?title=Programming_performance/hay.steve_Python&diff=63917Programming performance/hay.steve Python2021-02-06T15:19:25Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Hay.steve</p>
<hr />
<div>* '''Implementation time''': 1.5 hours.<br />
* '''Experience''': 3 days.<br />
* '''Comments''': I spent most of my time noodling on the syntax of Python and familiarizing myself with the documentation. I also spent some time getting the heap to work instead of taking multiple passes with that data. I originally said it took 2 hours, but I am bringing it down to 1.5 because I was eating dinner while and watching a movie while coding. Also, I came back later and spent a few minutes adding a verbosity feature as suggested in the problem statement.<br />
<br />
=== Code ===<br />
<br />
<code-python><br />
from heapq import heappush, heappop, nsmallest<br />
<br />
verbose=False<br />
filename = "gspc.txt"<br />
<br />
days = []<br />
<br />
for f in open(filename):<br />
if f[0] == '#':<br />
continue<br />
linelist = f.split(' ')<br />
heappush( days, linelist )<br />
<br />
cash = 10000.00<br />
previousClose = -1.0<br />
currentClose = 0.00<br />
<br />
shares = []<br />
<br />
beginningBalance = cash<br />
<br />
print "Beginning Balance:", cash<br />
while days != []:<br />
day = heappop( days )<br />
i = day[0]<br />
currentClose = float( day[4] )<br />
<br />
if previousClose != -1.0:<br />
percentGain = ( currentClose - previousClose ) / previousClose<br />
if percentGain < -0.03:<br />
numShares = 0.1 * cash / currentClose<br />
heappush( shares, (currentClose, numShares) )<br />
cash = 0.9 * cash<br />
if verbose: print "On", i, ", bought" , numShares , "shares at" , currentClose , "."<br />
<br />
else :<br />
while shares != [] and nsmallest(1, shares)[0][0] <= currentClose / 1.06:<br />
sell = heappop( shares )<br />
cash += sell[1] * currentClose<br />
if verbose: print "On", i, "sold" , sell[1] , "shares at" , currentClose , "."<br />
<br />
previousClose = currentClose<br />
<br />
while shares != []:<br />
sell = heappop( shares )<br />
cash += sell[1] * currentClose<br />
if verbose: print "Sold" , sell[1] , "shares at" , currentClose , "."<br />
<br />
print "Beginning balance:", beginningBalance<br />
print "Ending balance:", cash<br />
print "Percent Gain:", (cash-beginningBalance)/beginningBalance*100, "%."<br />
</code-python><br />
<br />
=== Some later refinements ===<br />
<code-python><br />
from heapq import heappush, heappop<br />
<br />
# iterates through a heap while destroying it (side effect)<br />
def heap_eater(heap):<br />
while heap: yield heappop( heap )<br />
<br />
# globals<br />
verbose = True<br />
filename = "gspc.txt"<br />
days = []<br />
positions = []<br />
beginningBalance = 10000.00<br />
cash = 10000.00<br />
close = 0.00<br />
<br />
# create the stock data heap<br />
for f in open(filename):<br />
if not f.startswith('#'):<br />
date, open, high, low, close, volume, adjClose = f.split(' ')<br />
day = ( date, float( close ) )<br />
heappush( days, day )<br />
<br />
print "Beginning Balance:", cash<br />
<br />
# iterate through the days<br />
startDate, oldClose = heappop( days )<br />
for day, close in heap_eater( days ):<br />
if close < 0.97 * oldClose:<br />
numShares = 0.1 * cash / close<br />
cash -= 0.1 * cash<br />
position = (close, numShares )<br />
heappush( positions, position )<br />
if verbose:<br />
print "On", day, ", bought" , numShares , "shares at" , close , "."<br />
else:<br />
for oldClose, numShares in heap_eater( positions ):<br />
if close >= 1.06 * oldClose:<br />
cash += numShares * close<br />
if verbose:<br />
print "On", day, "sold", numShares, "shares at", close, "."<br />
else:<br />
position = ( oldClose, numShares )<br />
heappush( positions, position )<br />
break<br />
oldClose = close<br />
<br />
# close out positions<br />
for price,qty in positions:<br />
cash += qty * close<br />
if verbose:<br />
print "Sold" , qty , "shares at" , close , "."<br />
<br />
print "Beginning balance:", beginningBalance<br />
print "Ending balance:", cash<br />
print "Percent Gain:", (cash-beginningBalance)/beginningBalance*100, "%."<br />
</code-python><br />
<br />
--[[User:Hay.steve|Hay.steve]] 01:53, 8 March 2007 (UTC)</div>Gwernhttps://wiki.haskell.org/index.php?title=Yhc/RTS/Bytecodes&diff=63915Yhc/RTS/Bytecodes2021-02-06T15:19:23Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by David Wahler</p>
<hr />
<div>{{Yhc}}<br />
<br />
The Yhc runtime is a stack-based spineless G-Machine (See [[Yhc/RTS/Machine]]). This page details the instruction set that the machine uses.<br />
<br />
A more up to date page is at http://www-users.cs.york.ac.uk/~ndm/yhc/bytecodes.html, which is automatially generated from the bytecode.xml file.<br />
<br />
Instructions have 'variants', which are different specializations of the instruction: For example if the general instruction is PUSH n then<br />
<br />
* PUSH_n is a specialized 1 byte instruction of PUSH n<br />
* PUSH_P1 n is a 2 byte instruction of PUSH n<br />
* PUSH_P2 n is a 3 byte instruction of PUSH n<br />
<br />
Some instructions don't have three byte versions. Here 'PUSH n' refers to the two byte version, or the general 'PUSH n' instruction, depending on context.<br />
<br />
The compiler will choose the smallest available bytecodes to encode any particular instruction.</div>Gwernhttps://wiki.haskell.org/index.php?title=GraphParserCombinators&diff=63916GraphParserCombinators2021-02-06T15:19:23Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by Smazanek</p>
<hr />
<div>[[Category:Combinators]]<br />
[[Category:Libraries]]<br />
==What are Graph Parser Combinators?==<br />
Graph Parser Combinators are a new and attractive approach to graph parsing. They are inspired by the popular concept of parser combinators for string languages like implemented in the libraries [[Polyparse]] or [[Parsec]]. <br />
<br />
Please have a look at the introductory talk that has been presented at IFL'07 (http://www.steffen-mazanek.de/dateien/talks/Graph_Parser_Combinators_IFL07.ppt).<br />
<br />
Please send any questions and suggestions to steffen.mazanek (at) unibw.de.<br />
<br />
==Where can I get them?==<br />
Be patient for the moment. A cabalized version of the library will be made available soon. If someone would like to host the darcs source of the library this would also be appreciated.</div>Gwernhttps://wiki.haskell.org/index.php?title=GHC/Concurrency/Flaws&diff=63914GHC/Concurrency/Flaws2021-02-06T15:19:22Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by ChrisKuklewicz</p>
<hr />
<div>[[Category:GHC|Concurrency]]<br />
<br />
= throwTo & block statements fixed in GHC 6.6.1 =<br />
<br />
The problem which used to be described here has been fixed in GHC HEAD and this will be included in GHC version 6.6.1<br />
<br />
I have built (Feb 9, 2007) the HEAD version of GHC and this problem is no longer present.<br />
<br />
See the ticket at [http://hackage.haskell.org/trac/ghc/ticket/1047] and the comments near the top of [http://darcs.haskell.org/ghc/rts/Exception.cmm].<br />
<br />
The description which was here has been deleted, but is still available in the historical views of this page.</div>Gwernhttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Sokoban/Solution_Jethr0&diff=63913Haskell Quiz/Sokoban/Solution Jethr02021-02-06T15:19:21Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by JohannesAhlmann</p>
<hr />
<div>[[Category:Haskell Quiz solutions|Countdown]]<br />
<br />
Obviously the most uncool kind of interface you could imagine. No readline, no clearscreen, you name it. But I was kinda reminded of the "good ole' days" when writing/playing this ;)<br />
<br />
<haskell><br />
module Main where<br />
<br />
import Prelude hiding (Either(..))<br />
import qualified Data.List as L<br />
import qualified Data.Char as C<br />
import Control.Monad<br />
import System.IO (getChar, hSetEcho, stdin)<br />
<br />
type Coord = (Int,Int)<br />
<br />
(|+|) :: Coord -> Coord -> Coord<br />
(a,b) |+| (c,d) = (a+c, b+d)<br />
<br />
data Move = Up | Down | Left | Right deriving (Show,Eq)<br />
<br />
data SokoState = SokoState {sWalls, sCrates, sStorages :: [Coord]<br />
,sWorker :: Coord<br />
,sSteps :: Int} <br />
deriving (Eq)<br />
<br />
modifyWalls f st = st{sWalls = f . sWalls $ st}<br />
modifyCrates f st = st{sCrates = f . sCrates $ st}<br />
modifyStorages f st = st{sStorages = f . sStorages $ st}<br />
modifyWorker f st = st{sWorker = f . sWorker $ st}<br />
modifySteps f st = st{sSteps = f . sSteps $ st}<br />
<br />
moveToCoord :: Move -> Coord<br />
moveToCoord Up = ( 0,-1)<br />
moveToCoord Down = ( 0, 1)<br />
moveToCoord Left = (-1, 0)<br />
moveToCoord Right = ( 1, 0)<br />
<br />
<br />
-- given a move and a state, compute the next state<br />
step :: Move -> SokoState -> SokoState<br />
step move state <br />
| isWall next1 = state<br />
| isCrate next1 =<br />
if isWall next2 || isCrate next2<br />
then state<br />
else modifyCrates ((next2:) . (filter (next1/=))) moveWorker<br />
| otherwise = moveWorker<br />
where SokoState{sWalls = walls, sCrates = crates, sWorker = worker} = state<br />
moveCoord = moveToCoord move<br />
next1 = worker |+| moveCoord<br />
next2 = next1 |+| moveCoord<br />
isCrate = (`elem` crates)<br />
isWall = (`elem` walls)<br />
moveWorker = modifySteps (+1) state{sWorker = next1}<br />
<br />
<br />
-- check if a level is solved by comparing crate and storage locations<br />
finished :: SokoState -> Bool<br />
finished SokoState{sCrates = cs, sStorages = ss} =<br />
L.sort cs == L.sort ss<br />
<br />
<br />
---<br />
<br />
<br />
drawState :: SokoState -> [String]<br />
drawState state@SokoState{sWalls = ws, sCrates = cs, sStorages = ss<br />
,sWorker = wrk, sSteps = steps} =<br />
show steps : [[charRep (x,y) | x <- [0..maxX]] | y <- [0..maxY]]<br />
where <br />
maxX = maximum $ map fst ws<br />
maxY = maximum $ map snd ws<br />
<br />
charRep coord<br />
| isWorker && isStorage = '+'<br />
| isCrate && isStorage = '*'<br />
| isWorker = '@'<br />
| isCrate = 'o'<br />
| isStorage = '.'<br />
| isWall = '#'<br />
| otherwise = ' '<br />
where isWorker = coord == wrk<br />
isCrate = coord `elem` cs<br />
isStorage = coord `elem` ss<br />
isWall = coord `elem` ws<br />
<br />
instance Show SokoState where<br />
show = unlines . drawState<br />
<br />
<br />
-- recreate a level from its ascii representation<br />
fromLevel :: [String] -> SokoState<br />
fromLevel level = foldl newCell emptyState $ (concat cells)<br />
where cells = map (\(y,xs) -> zipWith (\x c -> ((x,y),c)) [0..] xs) <br />
(zip [0..] level)<br />
newCell st (coord,char) = <br />
case char of<br />
'#' -> modifyWalls (coord:) st<br />
'o' -> modifyCrates (coord:) st<br />
'.' -> modifyStorages (coord:) st<br />
'*' -> modifyStorages (coord:) . modifyCrates (coord:) $ st<br />
'+' -> modifyStorages (coord:) . modifyWorker (const coord) $ st<br />
'@' -> modifyWorker (const coord) st<br />
otherwise -> st<br />
<br />
<br />
emptyState = SokoState {sWalls = []<br />
,sStorages = []<br />
,sCrates = []<br />
,sWorker = (0,0) -- *brr*<br />
,sSteps = 0<br />
}<br />
<br />
<br />
---<br />
<br />
<br />
-- ask for input until the level is solved<br />
-- TODO: add key to quit<br />
loop st = do<br />
print st<br />
c <- getChar<br />
let move = case c of <br />
'j' -> step Left<br />
'k' -> step Down<br />
'l' -> step Right<br />
'i' -> step Up<br />
otherwise -> id<br />
st' = move st<br />
if finished st' <br />
then print st' >> print "you won"<br />
else loop st' <br />
<br />
<br />
main = do<br />
hSetEcho stdin False<br />
loop $ fromLevel level_1<br />
hSetEcho stdin True<br />
<br />
<br />
---<br />
<br />
<br />
level_1 = [<br />
"#########",<br />
"# #",<br />
"# oo #",<br />
"# #. @#",<br />
"# . #",<br />
"#########"<br />
]<br />
<br />
</haskell></div>Gwernhttps://wiki.haskell.org/index.php?title=Humor/Dialogs&diff=63912Humor/Dialogs2021-02-06T15:19:20Z<p>Gwern: Reverted edits by Tomjaguarpaw (talk) to last revision by WillNess</p>
<hr />
<div>* '''Laziness'''<br />
<br />
Greedy Son: Dad, I need some new clothes. Gimme some money.<br />
Strict Dad: How many money do you need [pulls out wad of bills]<br />
Greedy Son: Mind your own business! I don't tell you how to earn the money,<br />
so don't tell me how to spend it! I'll ask Mom instead.<br />
Lazy Mom : Here's a credit card, Son. Just charge what you need.<br />
<br />
* '''Borrowing from the Future'''<br />
<br />
Student: I need a list of prime numbers<br />
Teacher: Easy. I'll give you the first one: 2. <br />
Now test each odd integer starting at 3 and try dividing by every prime up to its square root.<br />
Student: But I need to already know the primes in order to divide them into my candidates, don't I?<br />
Teacher: No problem, I have an infinite list of them! I'll make you a deal.<br />
I'll feed you these divisor primes as you need them, and you tell<br />
me whether your numerator ended up being prime.<br />
Student: OK, 3 is the next prime number<br />
Teacher: [Quickly writes this down on his list]<br />
Student: Hey, you're cheating! I'm the one doing all the work here! I'm<br />
generating primes faster than I need them, so really I'm stealing<br />
from myself. What's the use pretending I'm getting them from you?<br />
Teacher: No, I'm just doodling, I really do know all the primes. Your code<br />
is much simpler with me handing you the divisor primes anyway.<br />
What do you care where I get them from? It's no extra work for you!<br />
<br />
* '''Running in Circles'''<br />
<br />
Athlete: I run on an infinitely long track. I can go forever in a straight line without coming to the end.<br />
Trainer: Dummy, you're running on a treadmill. Look around: the walls aren't even moving.<br />
Athlete: I can't, the lights are off. The only thing I can see is the lighted path at my feet.<br />
Trainer: Moron! Don't you see that number "2" painted on the treadmill that keeps repeating every couple meters?<br />
Athlete: Of course, amazing how someone had the patience to keep painting the number 2 over and over.<br />
Trainer: Has it occurred to you that that is the same number "2" going by each time?<br />
Athlete: Prove it!<br />
Trainer: Easy, I'll just write a "3" next to it. See, the "2" is gone, now it's "23".<br />
Athlete: Now who d'you think you're fooling? You just knew the numbers ahead were all "23" after a certain point.<br />
Trainer: You're unbelievable! Don't you remember that there were numbers "2" before, and now it's "23"?<br />
Athlete: That's what ''I'''m saying!<br />
Trainer: Your logic is too lazy for me. You can't tell the difference between an infinite list and a cyclic one.<br />
Athlete: What do I care? I still get all the exercise I need!</div>Gwern