March 2014 - Beginners

Haskell code as DSL
by Rosario Borda 23 Mar '14

23 Mar '14

Hello Haskellers, what about insert haskell code as DSL in haskell program? as an example, in ghci: > eval [haskell| tail [0,1,2,3]|] [1,2,3] as intermediate step to get an interactive word-based italian translation of haskell: > eval [italian| coda [0,1,2,3]|] [1,2,3] I'm an italian primary school teacher and I would like to introduce my schoolchildren to FP using haskell... Thank you very much, see You son. Rosario

3 6

suggestions for code improvement
by Dennis Raddle 22 Mar '14

22 Mar '14

This is a fairly complex problem and I don't expect anyone to follow it all, but I thought I would just post it and see if anyone can immediately identify unidiomatic Haskell. The problem is this: I'm writing a program that does backtrack search to determine musical counterpoint. I begin by laying out a series of "cells" which are notes of *as yet undetermined* pitch but do have determined begin time and duration (and also the instrument playing them is known). The algorithm will find pitches for each cell in order to maximize a fitness function. Cells can overlap in time. The search algorithm is allowed to make some cells silent if that improves the final result. So each cell has a status which is one of the following "undecided," "determined a specific pitch," and "determined to be silent". data CellStatus = CellUndecided -- Undecided whether this cell will be a -- pitch or silent | CellSilent -- It has been decided that this cell will be -- silent | CellPitch Pitch -- This cell will be a specific pitch deriving(Show) The following code deals with only one aspect of the fitness function. When there are patterns in the music called "octave relations," it makes the solution a bad one that should be avoided. An octave relation is when some note, say a C, appears as a following C in a different octave and fclose in time. It's okay to repeat the same C, just not in a different octave. In some atonal styles of music octave relations need to be specially handled or avoided altogether. So this is an algorithm that determines if any octave relations are present. There are two kinds of octave relations between a cell A and a cell B (containing an octave relation). One happens when A and B overlap in time. Clearly that represent a very close juxtaposition of A and B and it's illegal. The next kind of octave relation happens when B follows A some time later, but there are very few intervening notes of other pitches. The idea is that if *a lot of notes* intervene, it distracts the ear and the octave relation is not audible. But if only a few intervene between A and B, the octave relation will really stand out. Another bit of trickery. Consider the cells that intervene between A and B; that is, notes that start *after the end of A* and *before the beginning of B*. Some of those might have a status of CellUndecided. Those notes count as helping to distract the ear because we know we are eventually going to fill them in. But cells with a status of CellSilent don't count. And of course, notes of CellPitch status count as distracting the ear (unless they represent an octave relation). Here's the code. If anyone actually wants to run this, I can email you some test data. import Data.Maybe import Data.Map(Map) import qualified Data.Map as M import qualified Data.List as L type Time = Int type Pitch = Int data Cell = Cell { endTime :: Time , cellStatus :: CellStatus } deriving(Show) data CellStatus = CellUndecided -- Undecided whether this cell will be a -- pitch or silent | CellSilent -- It has been decided that this cell will be -- silent | CellPitch Pitch -- This cell will be a specific pitch deriving(Show) -- maps a given Time to a list of Cells that *begin* at that time type TimeMap = Map Time [Cell] -- checkOctaveRelations -- -- Int :: all octave relations must be have at least this many -- intervening notes -- TimeMap :: map of Time to list of Cells at that time -- -- Result True if satisfies the condition that all octave relations -- have at least proper number of intervening notes (or there are no -- octave relations), False otherwise. -- checkOctaveRelations :: Int -> TimeMap -> Bool checkOctaveRelations condition timeMap = all checkOneTime . M.keys $ timeMap where -- check all notes at one begin time to verify they satisfy the condition. -- note that we assume this function is called with 'beginTime' in ascending -- time order, so we only check notes at or following 'beginTime' checkOneTime :: Int -> Bool checkOneTime beginTime | checkBunch cellsAtBeginTime = False -- this is the case that among -- all cells at 'beginTime', there -- are octave relations within -- them | otherwise = all checkOneCell cellsAtBeginTime where cellsAtBeginTime = fromJust . M.lookup beginTime $ timeMap checkOneCell :: Cell -> Bool checkOneCell cell -- the line below checks the case that any overlapping cells have -- octave relations | any (any (isOctRel cell)) overlappingCells = False -- otherwise count the number of intervening cells until the -- next octave relation | otherwise = case countFollowingNonOctRel cell followingCells of Nothing -> True -- no octave relatios were found following -- 'cell' - so condition is met Just count -> count >= condition where (Cell endTime _) = cell followingCells = M.elems . snd . M.split (endTime-1) $ timeMap overlappingCells = M.elems . M.filterWithKey (\k _ -> k > beginTime && k < endTime) $ timeMap -- countFollowingNonOctRel -- -- count the number N of cells that do not have an octave relation -- with input 'c' before encountering an octave relation. Result is Just N. -- if no octave relations are found at all, result is Nothing. countFollowingNonOctRel :: Cell -> [[Cell]] -> Maybe Int countFollowingNonOctRel c cellGroups = case L.findIndex (\cells -> any (isOctRel c) cells) cellGroups of Nothing -> Nothing Just idx -> Just . sum . map countCells . take idx $ cellGroups where countCells :: [Cell] -> Int countCells cells = sum . map countFn $ cells countFn (Cell _ CellSilent) = 0 -- silent cells are not distracting; don't count as any countFn _ = 1 -- other cells count as distracting -- checkBunch -- -- Check a group of cells that all occur at the same time for any octave -- relations in any pair of cells checkBunch :: [Cell] -> Bool checkBunch [] = False checkBunch (c:cs) = (any (\c' -> isOctRel c c') cs) || checkBunch cs isOctRel :: Cell -> Cell -> Bool isOctRel cell1 cell2 | isCellPitch cell1 && isCellPitch cell2 = isOctRel' cell1 cell2 | otherwise = False where isOctRel' (Cell _ (CellPitch p1)) (Cell _ (CellPitch p2)) = p1 /= p2 && p1 `mod` 12 == p2 `mod` 12 isCellPitch (Cell _ (CellPitch _)) = True isCellPitch _ = False isCellSilent (Cell _ CellSilent) = True isCellSilent _ = False

2 1

Installing Yesod!
by Gilberto Melfe 21 Mar '14

21 Mar '14

Hello People! I've been trying to get Yesod going! Updated cabal (as instructed). Installed the yesod-platform package. Next step, would be to install the yesod-bin package (for the yesod executable, server and stuff...)! But when I try: ./cabal install --dry-run yesod-bin I get these messages: Resolving dependencies... cabal: Could not resolve dependencies: trying: yesod-bin-1.2.7.3 (user goal) next goal: ghc (dependency of yesod-bin-1.2.7.3) Dependency tree exhaustively searched. I'm gonna get into trouble again, right? Can anyone tell me what to do next? Thank you very much! Gilberto

2 3

Re: [Haskell-beginners] Capture the notion of invertible
by Javran Cheng 21 Mar '14

21 Mar '14

I've tried that lens lib out, and it is exactly what I want. few examples in GHCi: λ> let pretty x = mapM_ print x λ> pretty mat [1,0,0,0,2] [0,3,0,4,0] [0,0,5,0,0] [0,6,0,7,0] [8,0,0,0,9] λ> let shiftL = filter (/= 0) >>> (++ repeat 0) >>> take 5 λ> over (iso transpose transpose) (map shiftL) mat [[1,3,5,4,2],[8,6,0,7,9],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] λ> pretty $ over (iso transpose transpose) (map shiftL) mat [1,3,5,4,2] [8,6,0,7,9] [0,0,0,0,0] [0,0,0,0,0] [0,0,0,0,0] λ> pretty $ over ((iso transpose transpose).(iso (map reverse) (map reverse) )) (map shiftL) mat [0,0,0,0,0] [0,0,0,0,0] [0,0,0,0,0] [1,3,0,4,2] [8,6,5,7,9] Off topic: In addition, as David Young commented in my codereview question: "rempty and rappend form a Category instance. " This comment makes perfect sense to me, because "monoid-like" reminds me of Data.Monoid, which does not totally capture what I know about monoid: monad is "just a monoid in the category of endofunctors" but Monad is not in any sense fit into a Monoid. Here I find that when I talk about "monoid-like", I actually refer to Category, and Monad is an instance of Category, which backs up my guess. In a word, can I say that when talking about reducing data (Sum, Product, etc.), I'm referring to Monoid, and when I talking about monoid-like composition, I'm referring to Category? Javran > Date: Tue, 18 Mar 2014 02:48:21 +0700 > From: Kim-Ee Yeoh <ky3(a)atamo.com> > To: The Haskell-Beginners Mailing List - Discussion of primarily > beginner-level topics related to Haskell <beginners(a)haskell.org> > Subject: Re: [Haskell-beginners] Capture the notion of invertible > functions > Message-ID: > <CAPY%2BZdTyj81gcUaZJfHGeta8rbjxup8ReKHJ%3Diy7ePzKkQPomQ(a)mail.gmail.com> > Content-Type: text/plain; charset="iso-8859-1" > > > When you're talking about invertible functions, the idea you're probably > reaching for is an isomorphism -- that is, we want the function to have > certain nice properties on top of just being a map from a -> b with an > inverse map from b -> a. > > The usual meaning of 'f is invertible' is that it is both left- and > right-invertible, thus making it bijective: see first bullet in [1]. > > Here you're alluding to f being merely left-invertible, something I don't > see mentioned in OP. > > > You also want the function to be a bijection, which is captured in the > notion of an isomorphism. > > I'm reminded of a reddit convo where the idea was tossed out that > semigroups should always be promoted to monoids [2]. > > I argued no. I also cited a case where a supposedly nicer monoid causes > more problems for a ghc hacker than the true semigroup [3]. > > Having structure is nice. And sometimes we just have to work with what's > given to us. > > Category theory calls a /monomorphism/ something that's strictly weaker > than left-invertible. An arrow that's (additionally) left-invertible > corresponds to a /split mono/. > > Hence in order of _decreasing_ niceness: Iso, Split mono, Mono. As research > uncovers more interesting phenomena, this sequence will continuing growing > to the right. > > We can't always impose that niceness because that nukes whatever we're > studying. So we gotta respect the situation. And given lemons, make > lemonade. > > > [1] > http://en.wikipedia.org/wiki/Bijection,_injection_and_surjection#Bijection > > [2] > http://www.reddit.com/r/haskell/comments/1ou06l/improving_applicative_donot… > > [3] > http://www.reddit.com/r/haskell/comments/1ou06l/improving_applicative_donot… -- Javran (Fang) Cheng

2 3

do Haskell programs have fewer bugs?
by Dennis Raddle 20 Mar '14

20 Mar '14

I was thinking about why it seems I can write Haskell code without bugs in a much easier way than imperative languages. Part of it is the strict type-checking, but I think there is something more. It's the potential for conciseness. I work hard when programming in Haskell to take advantage of language features that make my program concise. Somehow this leads me to think about it in a certain way. I know I'm on track as it gets smaller and smaller. And as it gets smaller, it leads me to think about my logic's cases and things like that. Certain patterns show up and I think about what those patterns mean for the structure of my problem. By the time I'm done with all that, I've analyzed my problem much more thoroughly than I would ever do in an imperative language. Dennis

8 8

Ambiguous type variables
by Dennis Raddle 20 Mar '14

20 Mar '14

I need help with an "ambiguous type variables" error. My problem domain is backtracking search to construct musical phrases by choosing notes that fulfill as many simultaneous criteria as possible. At the beginning, I always know that I need to choose N notes, and they will be chosen in a particular order, one at a time. I don't need to worry about cycles, therefore. There is a way of calculating a "goodness" score, given a series of the first M notes (where M ranges from 2 to N). I'm looking for the solution with the best score. Because my problem may be too large to do a complete search, I think it would be great to be able to do a combination of breadth and depth searching... sort of like a chess program that searches X moves ahead but not all the way to the end of the game. So I start with 1 note and do a complete search on all partial solutions with X notes looking for the best score (dealing with ties somehow, not sure yet how), then take the first note from the best solution, then do a complete search on all partial solutions with 2 to X+1 notes, and so forth until X=N. I have in mind many possible ways of representing phrases and "moves," so I wanted to implement my basic algorithm in a class. I need three data types: - "the data" : a representation of a solution with from 1 to N choices applied - "a choice" : a representation of a choice of note at a particular point in the phrase - "memo" : a way of tracking the best partial solution(s) found during this phase of the search Here's my code so far In the following the type variable "d" is "the data", "c" is "a choice" and "memo" is a memo. The error is Ambiguous type variables 'd0', 'c0' in the constraint: (Bt d0 c0 memo) arising from a use of 'newMemo' class Bt d c memo | d -> c, d -> memo where -- a solution state is checked against the best solutions stored in -- the memo, and possibly replaces or augments the list of best -- solutions. updateMemo :: memo -> d -> memo newMemo :: memo pickBest :: Int -> memo -> d isSolution :: d -> Bool isSolution x = stateSize x == solutionSize x -- number of choices applied so far stateSize :: d -> Int -- note that data of type 'd' includes an indication of what the -- final solution size is, something put there when d is initialized solutionSize :: d -> Int enumerateChoices :: d -> [c] -- choices available at this point in the -- construction of the state -- compute a goodness score scoreState :: d -> Double applyChoice :: d -> c -> d -- note that this is only partially implemented. Never mind that -- it's not complete or correct, I'm still trying to understand -- where my error arises. -- -- What is will eventually do: completely searches N levels deep -- before picking best score, then takes best partial solution, -- backs up N-1 levels and does another complete search, -- etc. finally displays solution with best score. limBacktrack :: Int -> d -> memo limBacktrack n d = limBacktrack' n newMemo d limBacktrack' :: Int -> memo -> d -> memo limBacktrack' nGoal memo d | stateSize d == nGoal = updateMemo memo d | otherwise = foldl g memo (enumerateChoices d) where -- g :: memo -> choice -> memo g memo choice = limBacktrack' nGoal memo (applyChoice d choice) The error is Ambiguous type variables 'd0', 'c0' in the constraint: (Bt d0 c0 memo) arising from a use of 'newMemo'

4 6

scotty - autorefresh / reload
by Miroslav Karpis 19 Mar '14

19 Mar '14

Hi, please is there a way how I could autorefresh / reload the page in scotty? A small example, where I would like to see that the time refreshes every second: {-# LANGUAGE OverloadedStrings #-} import Web.Scotty import Control.Monad.Trans (liftIO) import qualified Data.Text.Lazy as L (Text, pack) import Data.Time.Clock main = scotty 3005 $ do get "/" $ do time <- liftIO getTime html time getTime :: IO L.Text getTime = do utcTime <- getCurrentTime let timeText = L.pack $ show utcTime return timeText Cheers, M.

2 1

cabal install
by Gilberto Melfe 19 Mar '14

19 Mar '14

Good morning, Good people of the haskell community! I need to develop a web(site)/application. I want to try using Yesod. First thing i need to install it. (I already have the haskell-platform) So I run: cabal update It tells me that a new version of cabal-install is available; then I run: cabal install cabal-install After doing whatever it wants to do, successfully (at least that's what I think the logs say; I didn't notice any error) I update my path to: export PATH=/home/.../.cabal/bin:$PATH Everything is "OK" now! But I still don't have a cabal-install binary, and this update has been performed only for me (inside my user account)! Shouldn't I have a binary cabal-install to run? How can I update globally? (for all users of the system!) After this I'm going to try to install Yesod! And of course I would like to install for all users of the system (yes I'm the only one:-) but I'm just asking...) Can anyone help me out? Thank You very much! Gilberto

5 6

Capture the notion of invertible functions
by Javran Cheng 18 Mar '14

18 Mar '14

Hi, These days I find the notion of "inverse function" might be useful, the basic idea is to keep a pair of function f and g which are the inverse functions of each other and then manipulate on this pair of functions. The detail is both on my blog post: http://javran.github.io/posts/2014-03-17-capture-the-notion-of-invertible-f… and also code review: http://codereview.stackexchange.com/questions/44550/capture-the-notion-of-i… I think this is an interesting idea and want to share it with you. Advice and comments are welcomed and appreciated since I learn haskell through LYAH and some wiki pages and still not sure about what would be the most idiomatic way of doing it in haskell. Thanks, -- Javran (Fang) Cheng

3 3

backtracking search and memory usage
by Dennis Raddle 17 Mar '14

17 Mar '14

I want to implement backtracking search, but I wonder if I'm going to immediately run into memory usage problems if I don't use strict evaluation somewhere. I'm very hazy on how to implement strict evaluation. I'm thinking of creating a generic algorithm that looks something like the following. We have the concept of a data construct that can be built step by step. At each step are choices. We are investigating all the choices and finding series of choices that lead to a completed data construct or "solution." We want to generate a list of all solutions. (My Haskell syntax is rusty so there may be errors in the following.) class Construct a where enumerateChoices :: a -> [b] applyChoice :: a -> b -> a isSolution :: a -> Bool backtrack :: Construct a => a -> [a] backtrack c | isSolution c = [c] | otherwise = concat . map (backtrack . applyChoice c) . enumerateChoices $ c So my question is whether this is going to use a lot of memory to run, maybe by holding all partially solved data? Where would strict evaluation go?

2 2