September 2011 - Beginners

Iterating a monadic action with memoization
by Tim Cowlishaw 29 Jan '12

29 Jan '12

Hi all, I was wondering if any of you knew whether the following was possible, (I discussed this a little on #haskell at the weekend but didn't quite get to the bottom of it): Say I have a monadic action: > f :: a -> m a and an initial value of type a. I'd like to iterate this action and collect the results of each iteration in a list, as with 'iterate' on normal functions: > iterate (>>= f) . return $ a However, I would also like to memoize the intermediate results of the iteration, such that the entire iteration runs in O(n) time rather than O(n^2). This also implies a slight semantic difference, as side-effecting or non-deterministic actions will not be repeated in each iteration, while maintaining the laziness of the iteration function. Is it possible to do this? Many thanks, Tim

4 4

parser error coordinates transformation from preprocessed to original text
by Radoslav Dorcik 21 Oct '11

21 Oct '11

Hi! The parser function in my library is exposed to user which hides internally preprocessing & parsing. When parser error ocurr the coordinates are in preprocessed text, but library function user deserves to know coordinates in original text. Following is my application flow (simplified): {- User exposed library function -} parseLDIF :: String -> Either ParseError LDIF parseLDIF xs = myParser $ myPreprocessor xs {- Expects the preprocessed input -} myParser :: String -> Either ParseError LDIF {- Remove comments and unwarp lines; No new text added only removed -} myPreprocessor :: String -> String My approach I'm going to implement is to keep information what myProcessor did on text (some kind of journal of preprocessing). In the case of error this journal will be used for original text coordinates calculation. myPreprocessor :: String -> (String,[PreprocessorOperation]) Anyway, I have feeling that I'm doing something very wrong... reason for this email. What is the common approach to transform error coordinates from preprocessed to original text ? Is that common to separate preprocessing & parsing phase ? Thanks, Rado

2 3

A post about Currying and Partial application
by Petar Radosevic 04 Oct '11

04 Oct '11

Hi, Like most here I'm also learning the beautiful language called Haskell and arrived at the subject of Currying. To see if I really understood the concept, I decided to write a blog post about it. http://s3.wunki.org/posts/2011-09-30-curry-and-its-partial-application.html I hope it helps some of the beginners here. Please take a look at it and let me know if I'm wrong or if I missed something. Thank you! -- Petar Radošević, Programmer wunki.org | @wunki

5 8

clarity and complexity of Haskell code?
by Gregory Guthrie 29 Sep '11

29 Sep '11

I always enjoy and tout the clarity and simplicity of the declarative style of functional programming, and with that also Haskell. But it seems that although the wonderfully short and clear examples dominate early learning and usage, the forums like this and café are dominated by examples more like this: import Data.Enumerator (run_, ($$), (=$)) import Data.Enumerator.Binary (enumHandle, iterHandle) import Data.Enumerator.List as EL (map) import Data.ByteString as B (map) import Data.Bits (complement) import System.IO (withFile, IOMode(..)) main = withFile "infile" ReadMode $ \inh -> withFile "outfile" WriteMode $ \outh -> do run_ (enumHandle 4096 inh $$ EL.map (B.map complement) =$ iterHandle outh) And many more - looks more like APL or Perl to me. :) Certainly not the Python'ish model of "anyone can read this, and it is clear what it does". Seems like the assertion that FP is easier and more clear is true at introductory levels, but there are some subsequent big gradients in the learning and usage curve. I use it only in very simple and small programs, so wondered about the observations on this from more experienced experts. I wonder if any studies have been done to quantify and measure the complexity of programs in Haskell, as a way to assess this property.

6 5

Builds with cabal, but not with GHC
by Amy de Buitléir 28 Sep '11

28 Sep '11

I'm getting some weird errors when I try to compile this with GHC, or load it in GHCi, but it compiles (and runs) just fine using cabal. Here's the file... ********** FILE Test.hs: ********** module Main where import Control.Monad.Error ( runErrorT, ErrorT, join, liftIO ) import Data.ConfigFile ( get, CPError, emptyCP, readfile ) data Configuration = Configuration { popDir :: FilePath, username :: String, sleepTime :: Int } deriving Show parseConfig :: ErrorT CPError IO Configuration parseConfig = do cp <- join $ liftIO $ readfile emptyCP "/etc/creatur-daemon.conf" u <- Data.ConfigFile.get cp "DEFAULT" "user" pd <- Data.ConfigFile.get cp "DEFAULT" "dir" st <- Data.ConfigFile.get cp "DEFAULT" "sleeptime" return $ Configuration { popDir = pd, username = u, sleepTime = st } main :: IO () main = do rv <- runErrorT parseConfig case rv of Left (_, msg) -> putStrLn msg Right config -> print config ********** When I compile it with ghc, I get the following: $ ghc -hide-package monads-fd Test.hs [1 of 1] Compiling Main ( Test.hs, Test.o ) Test.hs:20:9: No instance for (mtl-1.1.1.1:Control.Monad.Error.Class.MonadError CPError (ErrorT CPError IO)) arising from a use of `get' Possible fix: add an instance declaration for (mtl-1.1.1.1:Control.Monad.Error.Class.MonadError CPError (ErrorT CPError IO)) In a stmt of a 'do' expression: st <- get cp "DEFAULT" "sleeptime" In the expression: do { cp <- join $ liftIO $ readfile emptyCP "/etc/creatur-daemon.conf"; u <- get cp "DEFAULT" "user"; pd <- get cp "DEFAULT" "dir"; st <- get cp "DEFAULT" "sleeptime"; .... } In an equation for `parseConfig': parseConfig = do { cp <- join $ liftIO $ readfile emptyCP "/etc/creatur-daemon.conf"; u <- get cp "DEFAULT" "user"; pd <- get cp "DEFAULT" "dir"; .... } Test.hs:21:3: No instance for (Error (CPErrorData, String)) arising from a use of `return' Possible fix: add an instance declaration for (Error (CPErrorData, String)) In the expression: return In the expression: return $ Configuration {popDir = pd, username = u, sleepTime = st} In the expression: do { cp <- join $ liftIO $ readfile emptyCP "/etc/creatur-daemon.conf"; u <- get cp "DEFAULT" "user"; pd <- get cp "DEFAULT" "dir"; st <- get cp "DEFAULT" "sleeptime"; .... } I tried adding the instance declarations, but I don't think I did it right because I then had to add a bunch of imports, and the problems just snowballed. With this cabal file, I can do "cabal install", and the program compiles and runs just fine. ********** FILE: Creatur.cabal ********** Name: Creatur Version: 2.0 Description: Créatúr License: OtherLicense License-file: LICENSE Author: Amy de Buitléir Maintainer: amy(a)nualeargais.ie Build-Type: Simple Cabal-Version: >=1.2 Executable amy-test Main-Is: Test.hs GHC-Options: -Wall -Werror Build-Depends: base >= 4 && < 5, mtl ==1.1.*, ConfigFile ==1.0.* ********** Can anyone tell me how to modify the code so it will compile? Thank you in advance.

4 6

sorting almost sorted list
by Dennis Raddle 28 Sep '11

28 Sep '11

I have a problem from music. I have a list of notes sorted by begin time. I want to sort them by end time. Notes that are sorted by begin time are usually close to sorted by end time, because notes tend to cluster within a small range of durations. What algorithms are available to me (hopefully in a library) that are good with this kind of thing? Dennis

4 3

Re: [Haskell-beginners] sorting almost sorted list
by David Fletcher 28 Sep '11

28 Sep '11

On Mon, 26 Sep 2011 19:46:29 -0700 Dennis Raddle wrote: > I have a problem from music. I have a list of notes sorted by begin > time. I want to sort them by end time. > > Notes that are sorted by begin time are usually close to sorted by end > time, because notes tend to cluster within a small range of durations. > > What algorithms are available to me (hopefully in a library) that are > good with this kind of thing? > How about something like this? It keeps an output queue sorted by the end time. We allow notes to exit the queue and become part of the result as soon as we can guarantee we aren't going to see any notes with an earlier end time. data Note = Note { begin :: Integer, end :: Integer } noteSort :: [Note] -> [Note] noteSort = noteSort' [] noteSort' :: [Note] -> [Note] -> [Note] noteSort' outq [] = outq noteSort' outq (x:xs) = out ++ noteSort' outq'' xs where (out, outq') = span (`entirelyBefore` x) outq outq'' = insertBy (comparing end) x outq' entirelyBefore :: Note -> Note -> Bool a `entirelyBefore` b = end a < begin b Here I've used a sorted list for the queue, so in the worst case (with a note that lasts for the whole piece), it degrades into an insertion sort of the whole thing. But you could replace that list with a heap, and then it would degrade into a heapsort. David.

1 0

Re: [Haskell-beginners] sorting almost sorted list
by Yitzchak Gale 28 Sep '11

28 Sep '11

I wrote: > Can you guarantee for some value of m that for each note N, > only the first m notes following N might end earlier than N? > If so, then the following simple algorithm is linear > and runs in constant space. You could then use: > sortAlmostBy m (comparing endTime) > ...You might be able to do a little better than this. After running some tests, it seems empirically that you can use m `div` 2 instead of m for lists of even length, which gives you a nice speedup for larger values of m. For lists of prime length, the best you can do seems to be m-1. It's more complicated for lists of non-prime odd length. I can't immediately see why any of that is true. Daniel to the rescue perhaps? test n k = fmap (all isSorted . map (sortAlmostBy n compare)) $ rands k isSorted xs = and . zipWith (<=) xs $ drop 1 xs rands d = fmap (take 100 . map (concat . zipWith (map . (+)) [0,d ..] . chunksOf d) . chunksOf 1000 . randomRs (0, d-1)) newStdGen Thanks, Yitz

2 6

Re: [Haskell-beginners] Functional programming principles at higher levels?
by Christopher Howard 26 Sep '11

26 Sep '11

On 09/24/2011 09:12 PM, Mike Meyer wrote: > > Actually, functional programming and the higher math are separate > things. Haskell (and I expect the similar languages) have a lot of > math in their documentation. But that's not true for other functional > languages, like Clojure or Scheme. With a background in those > languages, I didn't have much trouble with the functional nature of > haskell. But I'm still trying to recall the graduate math courses I > took long time ago in a state far, far different from today. > Really? I'll confess I'm a bit surprised to hear that perspective. I don't know anything about Clojure or Scheme. But I found in trying to understand Haskell that it really is all about higher math. Once I finally gave up on "learnyouahaskell" and other ridiculous tutorials, I found the real functional programming textbooks, and discovered that it all starts with lambda calculus; all the explanations are given in set theory notation, with occasionally comparisons to integral and differential calculus for illustration, with very specific rules regarding substitution and reduction and normal forms. I'm still trying to figure out what all those combinators are about! And it is all rested on mathematical proofs, usually inductive. And that is just the lambda calculus aspect. Then we move on to type theory (!!!) plus the various types of polymorphism, and then on to a number of other topics that I don't know enough about to even mention intelligibly. -- frigidcode.com theologia.indicium.us

5 6

Re: [Haskell-beginners] clarity and complexity of Haskell
by Gregory Guthrie 26 Sep '11

26 Sep '11

I agree that the paradigm shift is an issue, but I don't think it is the main element for the things that I am pointing out. And I do think that Functional languages with their declarative style, type inference, polymorphism, lack of state, all do make FP style clearer and simpler. I come from SML (fairly casual usage), and I think the bump in learning curve (and thus clarity in reading) at least for me in Haskell is the shift to Monads and Applicatives, with their unfamiliar syntax of new operators, and semantics on those. Most other things in FP are a fairly simple shift; the domains and operations, and expression & operator syntax, and recursion, etc. are fairly familiar, just a different style is needed. Of course the Lazy nature of Haskell does require some adjustment in the underlying model and understanding of evaluation. When shifting to Functors, Applicatives, Monads, Arrows, all of these elements change significantly and there is no corresponding familiar domain for reference. Yes, I certainly agree that once one gets familiar with this model and syntax, and new operators and usage, it is powerful and readable. Just as APL, Perl, ... I agree with the earlier response that the increasing number of unfamiliar operators in Haskell increases the learning curse, albeit for their associated power in usage. I think that APL had a similar characteristic. :) This was not a complaint, but just an observation; my interest is mainly in teaching Introductory FP as a part of various comparative programming languages. No language wars intended; I was just interested in calibration from the views and experiences of more expert and experienced Haskell'ers.

1 0