August 2012 - Beginners

Lazy evaluation and list comprehensions
by Obscaenvs 08 Aug '12

08 Aug '12

Hi fellow Haskellers! Trying literary style here, lets just hope it plays well with your email clients. Suppose we define a list - somewhat arbitrarily - as > xs = [1..42] :: [Int] Next, we let x and ys be > x = 17 -- also somewhat arbitrarily > ys = [ y | y <- xs, y >= x ] My question: in which WHNF state is ys? y and x are evaluated in applying >= to them - at least in this particular instance of Ord (Int). Are these evaluated values then copied to the new list ys, or are they just stored as thunks? I would guess that they are just thunked, and that the state of ys is [*thunk*,*thunk*,...,*thunk*] since it cannot be known beforehand to what extent the predicate reduces its arguments (in this case >= ), but I don't know for sure. I thought I had sufficient knowledge about thunks, WHNF, NF and lazy evaluation, but this one does me in. I guess it is because I haven't trawled through Okasaki's book yet :)

2 1

Getting Haddock to Link Against Dependencies
by Alec Story 07 Aug '12

07 Aug '12

I'm trying to use haddock on a module I'm building, and while cabal haddockgenerates the documentation I want, it won't link to documentation of dependencies (for example, Data.Word in base). Instead, I get messages like: Warning: My.Module: could not find link destinations for: GHC.Types.IO Control.Concurrent.Chan.Chan Data.ByteString.Lazy.Internal.ByteString GHC.Classes.Eq GHC.Classes.Ord GHC.Show.Show Data.Monoid.Monoid GHC.Word.Word16 GHC.Word.Word8 GHC.Word.Word32 GHC.Types.Int GHC.Integer.Type.Integer GHC.Word.Word64 GHC.Enum.Enum Data.Binary.Binary Data.Maybe.Maybe I've had this working before, but I just moved to a different computer. I'd like to have the documentation available so that I can keep working even if I go offline. Any idea of how to fix this? I can compile and run the code fine, so the dependencies are installed. -- Alec Story Cornell University Biological Sciences, Computer Science 2012

1 0

Correction needed in Real World Haskell, chapter 24 (Concurrency and Parallelism)?
by Obscaenvs 07 Aug '12

07 Aug '12

At http://book.realworldhaskell.org/read/concurrent-and-multicore-programming.… , just after the code for `sillySort`, it says <quote> "In this mistaken example, we evaluate each sorted sublist to WHNF. Since the outermost constructor in each case is just a single list constructor, we are in fact only forcing the evaluation of the first element of each sorted sublist! Every other element of each list remains unevaluated." </quote> My ruminations on the subject ended up in the following analysis, which is quite contrary to that of the authors': In the general case of the type inside the list being just an instance of Ord, it is *not* the case that the first element is necessarily evaluated; it is evaluated just enough (along with the elements of the *rest* of the lists greater and lesser) to enable < and >= to do their job inside the list comprehensions. Now, if these elements are Int:s or Integer:s then certainly, yes, the first element *is* evaluated, but so is the rest of the elements of the lists greater and lesser. So, greater and lesser are not only reduced to WHNF, but to NF in the case of sillySort working on [Int] or [Integer]. Am I mistaken in my analysis? If so, where? /Fredrik -- haskellBlog: http://www.monoid.se/categories/haskell/

1 0

DPH installation and LLVM
by listig314＠gmail.com 06 Aug '12

06 Aug '12

Dear all, being completely new to Haskell I wanted to explore what DPH is about, so I tried to install it via cabal install dph-examples but the installation process stops once it gets to installing the actual examples package: --- Building dph-examples-0.6.1.3... Preprocessing executable 'dph-spectral-smvm' for dph-examples-0.6.1.3... [1 of 3] Compiling Vectorised ( examples/spectral/SMVM/dph/Vectorised.hs, dist/build/dph-spectral-smvm/dph-spectral-smvm-tmp/Vectorised.o ) exprType TYPE ghc-prim:GHC.Types.Double{(w) tc 3u} exprType TYPE ghc-prim:GHC.Types.Double{(w) tc 3u} exprType TYPE ghc-prim:GHC.Types.Double{(w) tc 3u} exprType TYPE ghc-prim:GHC.Types.Double{(w) tc 3u} exprType TYPE ghc-prim:GHC.Types.Double{(w) tc 3u} exprType TYPE (ghc-prim:GHC.Types.Int{(w) tc 3J}, ghc-prim:GHC.Types.Double{(w) tc 3u}) Warning: Couldn't figure out LLVM version! Make sure you have installed LLVM ghc: could not execute: opt cabal: Error: some packages failed to install: dph-examples-0.6.1.3 failed during the building phase. The exception was: ExitFailure 1 --- This is the rest of my setup: Mac OS X 10.7.4 Xcode 4.3.3 + Command Line Tools (from within Xcode) Haskell Platform 2012.2.0.0 32bit Why doesn't Haskell find the LLVM compiler? Is there a way to install the remaining examples without LLVM compilation? Thanks, Oliver

3 6

Re: [Haskell-beginners] Using a concept from Category Theory to enable you to come back home after your function has taken you somewhere
by Costello, Roger L. 05 Aug '12

05 Aug '12

Hi Miguel, First note that I am very much a beginner at Category Theory. I am just sharing what I learn. > How do you know that a Haskell function is injective? I don't think it's possible to write a function which checks if another function is injective or not . A function is injective if each input value (domain) yields a different output value (codomain). So if the set of inputs is finite, then it should be possible to write a function that loops over each input value and checks that its output is distinct from all other outputs. > How to automatically get the inverse of a Haskell function? That's a great question. I don't know the answer to that. Anyone else have an idea? /Roger

3 2

Using a concept from Category Theory to enable you to come back home after your function has taken you somewhere
by Costello, Roger L. 04 Aug '12

04 Aug '12

Hi Folks, When I go hiking, I want to be able to retrace my steps and get back to my starting point. When I go to a store, I want to be able to return home. When I swim out from the shore, I want to be able to get back to the shore. Going somewhere and then coming back to where one started is important in life. And it is important in mathematics. And it is important in functional programming. If a function maps a set of elements (the domain) to a set of values (the codomain) then it is often useful to have another function that can take the elements in the codomain and send them back to their original domain values. The latter is called the inverse function. In order for a function to have an inverse function, it must possess two important properties, which I explain now. Let the domain be the set of days of the week. In Haskell one can create the set using a data type definition such as this: data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday Let the codomain be the set of breakfasts. One can create this set using a data type definition such as this: data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage Now I create a function that maps each element of the domain to a value in the codomain. Here is one such function. The first line is the function signature and the following lines is the function definition: f :: Day -> Breakfast f Monday = Eggs f Tuesday = Cereal f Wednesday = Toast f Thursday = Oatmeal f Friday = Pastry f Saturday = Ham f Sunday = Grits An important thing to observe about the function is that no two elements in the domain map to the same codomain value. This function is called an injective function. [Definition] An injective function is one such that no two elements in the domain map to the same value in the codomain. Contrast with the following function, where two elements from the domain -- Monday and Tuesday -- both map to the same codomain value -- Eggs. g :: Day -> Breakfast g Monday = Eggs g Tuesday = Eggs g Wednesday = Toast g Thursday = Oatmeal g Friday = Pastry g Saturday = Ham g Sunday = Grits The function is not injective. Can you see a problem with creating an inverse function for g :: Day -> Breakfast? Specifically, what would an inverse function do with Eggs? Map it to Monday? Or map it to Tuesday? That is a problem. [Important] If a function does not have the injective property then it cannot have an inverse function. In other words, I can't find my way back home. There is a second property that a function must possess in order for it to have an inverse function. I explain that next. Did you notice in the codomain that there are 8 values: data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage So there are more values in the codomain than in the domain. In function f :: Day -> Breakfast there is no domain element that mapped to the codomain value Sausage. So what would an inverse function do with Sausage? Map it to Monday? Tuesday? What? The function is not surjective. [Definition] A surjective function is one such that for each element in the codomain there is at least one element in the domain that maps to it. [Important] If a function does not have the surjective property, then it does not have an inverse function. [Important] In order for a function to have an inverse function, it must be both injective and surjective. One final piece of terminology: a function that is both injective and surjective is said to be bijective. So, in order for a function to have an inverse function, it must be bijective. Recap: if you want to be able to come back home after your function has taken you somewhere, then design your function to possess the properties of injectivity and surjectivity. /Roger

2 1

growing trees
by Jeff Lasslett 04 Aug '12

04 Aug '12

Hello again, There were a few details I accidentally omitted from my initial email. I've attached my code again. As I mentioned in my first message on this subject, I'm just after some guidance on ways to improve upon what I've written. How can I make it clearer, more concise?? Here's a transcript of a ghci session showing how I generate a tree from a list of associations: *AssocTree> let related = filterUnrelated assocs *AssocTree> let t = growTree ( Node r [] ) related *AssocTree> printTree t root | +- C | | | +- f | | | +- e | | | | | `- m | | | `- D | | | +- g | | | | | +- i | | | | | `- j | | | | | `- k | | | `- h | +- B | `- A

1 0

GHC / system libraries
by Christopher Howard 04 Aug '12

04 Aug '12

I know that GHC allows you to create shared libraries and create binaries that use shared libraries, because I asked that question some time ago on this list. However, I was wondering: can the GHC "standard libraries" be decoupled from the compiler? I.e., so you can install the libraries and the binaries on a system without the compiler being installed? I use a source-based distro so it is of little relevance to me. However, I was discussing Haskell apps online with some friends who use binary-based distros and had to admit that I wasn't clear on this point. -- frigidcode.com indicium.us

1 0

growing trees
by Jeff Lasslett 03 Aug '12

03 Aug '12

Greetings, For my own edification I have written a few functions for creating a tree from a list of 'associations'. An association is defined as data Assoc = Assoc { label :: String , assocId :: Int , assocPid :: Int } deriving ( Show ) where assocId is an int that uniquely identifies a node, and assocPid is the id of that node's parent. The idea is to feed an array of these associations into a function and get a Data.Tree Assoc out. So I have code that does the job ... ... but it's not very good. I thought the problem might be solved with a fold, but that proved difficult due to the Assocs not being in a suitable insertion order. Perhaps the routines can be improved such that the array order doesn't matter. Any advice, or better versions would be appreciated. thanks, Jeff PS: AssocTree.hs should be attached.

1 0

Why is the the transpose function in Data.List more complicated?
by KC 03 Aug '12

03 Aug '12

Transpose in Data.List is the following: transpose :: [[a]] -> [[a]] transpose [] = [] transpose ([] : xss) = transpose xss transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss]) Yet this seems to work. transp :: [[b]] -> [[b]] transp ([]:_) = [] transp rows = map head rows : transp (map tail rows) Why is the the transpose function in Data.List more complicated? -- -- Regards, KC

2 1