- Beginners - Haskell.org

short function to remove and replace an item
by Michael P Mossey 01 Apr '09

01 Apr '09

What if I have a list xs, and I want to remove one item and replace it with another? The item to remove can be detected by a predicate function. The order of the items doesn't matter. How about this: replaceItem :: (a -> Bool) -> a -> [a] -> [a] replaceItem p new xs = new : snd (partition p xs) This will actually replace all items that match the predicate with one copy of 'new'. It will also prepend 'new' even if no items match the predicate. For another challenge, can someone explain to me how to write this in point-free style? Thanks, Mike

4 4

Basic Parsec question
by Zachary Turner 01 Apr '09

01 Apr '09

Hi, I downloaded the package lispparser to, well, parse lisp code. I really have absolutely no idea what I'm doing though. I can look at the source of the module and see that it's exporting a single data type called LispVal and a single function called parseExpr, so somehow I should be able to pass an arbitrary block of lisp code into this function and get back a LispVal. But for the life of me I can't figure out how. I've looked at the documentation but I get even more confused because it links me to the Parsec documentation which is probably way over my head. Basically I just want a simple function: parse :: String -> LispVal parse expr = ??? presumably by making some use of the exported 'thing' (since I'm not really sure how to interpret its type) parseExpr :: Parser LispVal Thanks for any help

2 2

Re: [Haskell-cafe] abou the Godel Numbering for untyped lambda calculus
by Dan Weston 31 Mar '09

31 Mar '09

DISCLAIMER: The last I studied this was over 20 years ago, so my brain is seriously rusty. You are warned... > you mean the godel function (denoted by # and generally will be in type, > #:term -> number ?) is a kind of functions instead of a particular > function? No. The Godel mirror function (as defined by Godel) is a single function, the product of primes (whose ordering gives the position in the string) with exponents (giving the symbol at that position). However, I think any total injective function with partial injective inverse will do. Don't get hung up on the details of the mirroring (Godel doesn't). Once you accept that it can be done, there is no need to actually do it. There is nothing magic about integers, beyond the fact that elementary arithmetic is "well understood" by humans and should not have inconsistencies (it probably doesn't, but we can't prove it within any language more intuitive than arithmetic, so why should be believe the proof in that language?). Importantly, all but the last step of the proof can be encoded as primitive recursive functions, meaning that they always halt within a predetermined number of steps (satisfying the Finitists). Only the last step cannot be so limited. This is a clear example where non-finite mathematics has demonstrably more power in a fundamentally important way. Why bother going through this encoding? The main reason for the encoding is to overcome the fundamental limitation of structural induction whereby there is no "this" smaller than this. I.e. quoting a sentence only makes it longer. With functions on integers, this limitation is removed, so that although there is no string saying "This statement is not true", (since "This statement" != "\"This statement is not true\""), there *is* some function taking the Godel number of the unquoted This to the Godel number of the string to which it refers. Doing so takes some bit of cleverness, but the original proof in German is only about 8 pages long, as I recall. If we don't go with mirroring and just use strings, we need to introduce some equivalent trick, namely named functions. In a language without pointers and only lambda expressions, there is no way to refer to oneself without repeating the quote in infinite regression. For instance "\x -> 3333333" is longer than "333333". You cannot talk about a string without embedding it as a substring. However, once you add named functions to your metalanguage (Haskell): f 3 = 33333333 Then the string "f 3" is shorter than the string "xxxxxxx". Suppose f 4 = "~xxxxxxx". Now one can talk about the other with the shorter string on the left: length "f 3" < length "~xxxxxxx" but also length "f 4" < length "xxxxxxx". A longer string can talk about a shorter string (but not vice versa), so this mapping is critical to overcoming the limitation about talking about oneself. After that, the rest is easy: encode the Liar's Paradox and voila. once we have the encoding of a language, and construct functions to encode proof transformations, we can reduce derivability to a simple predicate derivable :: String -> Bool and look for some formula f such that derivable (f) == False and derivable("~" ++ f) == False. Godel's First Incompleteness Theorem merely says that there is some integer (which mirrors some well-formed formula) not in the set of integers that mirror "derivable theorems", making your system incomplete. Moreover, if you remedy this situation by adding this integer to the set as an axiom, you immediately can derive another integer which mirrors its negated formula, making your system inconsistent. The metasystem (with symbols for derivable, transformation rules like modus ponens, and the like), are not part of the formal system, but in the metalanguage. By encoding this metalanguage as well and redoing the above, you get Godel's Second Incompleteness Theorem, which says that no system can prove its own consistency, and if an axion is added to assert consistency, you can immediately also prove its negation, making it unsound. Don't look for a hat trick. Encoding the meta-meta-system buys you nothing extra. That's about all I can remember without hypnosis, and I'm afraid of what I might say under hypnosis... :) Dan Algebras Math wrote: > you mean the godel function (denoted by # and generally will be in type, > #:term -> number ?) is a kind of functions instead of a particular > function? If so, what kind of property this kinds of functions have? any > limitation? how capable they will be? > > Thanks > > alg > > On Tue, Mar 31, 2009 at 4:01 AM, Dan Weston <westondan(a)imageworks.com > <mailto:westondan@imageworks.com>> wrote: > > I can't tell exactly what you're asking, but I'll give it a try! :) > > primes :: [Integer] > primes = [2,3,5,7,11,13,17,19,23,29,31,undefined] > > godel :: String -> Integer > godel = product . zipWith (^) primes . map (toInteger . ord) > > -- Here is the identity function (note that double backslash is a > single character > godel "\\x -> x" > 1629920514342441477851613634029704631135430980107335428017064836156091059806450516131002598452000651374890570022191128551421788559667251656959733380229796871976693176094558797489489057311763922507760911447493016261397754567695234219623056037447490713525815311253273691703346455275115486717580778238094808661626709709766328915159206002675716287759792707200037683200000000000000000000000000000000 > > -- = 2^92 * 3^120 * 5^32 * 7^45 * 11^62 * 13^32 * 17^120 > > ungodel :: Integer -> String > -- ungodel . godel = id > > (See http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic > for why this works). > > These numbers get large quickly, but are finite for any finite > string of finite alphabet. > > godel is a total function (every string has a unique integer), and > its inverse (an exercise to the reader involving prime factor > decomposition) would also be total if the alphabet were infinite (so > that ord would be total). > > Frankly, I wouldn't know how to begin encoding the godel numbering > in the type system (shudder!), but being that it is a total > primitive recursive function, I suppose there is no theoretical > impediment. > > In contrast, Godel's Theorems themselves cannot be so encoded > because the last step involves a general recursive function. > > Dan > > > Algebras Math wrote: > > Hi all, > > I am reading the book "The lambda calculus: Its syntax and > Semantics" in the chapter about Godel Numbering but I am > confused in some points. > > We know for Church Numerals, we have Cn = \fx.f^n(x) for some > n>=0, i.e. C0 = \fx.x and C1 = \fx.fx. > > From the above definition, I could guess the purpose of this > kind of encoding is trying to encode numeral via terms. > > How about the Godel Numbering? From definition we know people > say #M is the godel number of M and we also have [M] = C#M to > enjoy the second fixed point theorem : for all F there exists X > s.t. F[X] = X. > > What the mapping function # is standing for? How could I use it? > What the #M will be? How to make use of the Godel Numbering? > > Thank you very much! > > alg > > >

1 0

What is the Haskell idiom for "if then else if then"
by Peter Hickman 31 Mar '09

31 Mar '09

I've just written this piece of code if r < 0 then LEFT else if r > 0 then RIGHT else STRAIGHT which works just fine but it does look rather clunky (as it would in any language I suppose). Is there a Haskell idiom for this type of code?

4 3

abou the Godel Numbering for untyped lambda calculus
by Algebras Math 30 Mar '09

30 Mar '09

Hi all, I am reading the book "The lambda calculus: Its syntax and Semantics" in the chapter about Godel Numbering but I am confused in some points. We know for Church Numerals, we have Cn = \fx.f^n(x) for some n>=0, i.e. C0= \fx.x and C 1 = \fx.fx. >From the above definition, I could guess the purpose of this kind of encoding is trying to encode numeral via terms. How about the Godel Numbering? From definition we know people say #M is the godel number of M and we also have [M] = C#M to enjoy the second fixed point theorem : for all F there exists X s.t. F[X] = X. What the mapping function # is standing for? How could I use it? What the #M will be? How to make use of the Godel Numbering? Thank you very much! alg

2 1

Need help to edit the Haskell script in Winhugs and documentation.
by RAJESH DALSANIYA 30 Mar '09

30 Mar '09

* * *Both sections relate to the case study: Index for a document of text.* * * *SECTION A: * * * *Given the attached Haskell code which produces an index of words, make the following alterations by modifying existing functions and including new functions where necessary – parts 1) to 5):* * * *1) **Where a word occurs N times on the same line, ensure that the line number occurs n times in the index entry for that word. * * * *2) **Allow words to be hyphenated and treat a hyphenated word as a single word. However, for those words which are split over two lines, treat a split word as a single word without the hyphen. * * * *3) **Treat a capitalised word (one or more capitals) as being different from the word in all lower case (but they should still be sorted alphabetically) – unless it is at the start of a sentence with only the initial letter capitalised. A sentence is terminated by a ‘.’, ‘?’ or ‘!’. * * * *4) **Make the output more readable in the form of an index table in columns with appropriate spacing and without brackets. * * * *5) **Include a user-friendly menu, so that the user can choose input/output file names or default files, and choose to rerun or exit. * * * *Parts 1) to 5) may be developed in any order. * * * * * *SECTION B:* * * *6) **For your version of function, makeIndex (only), show how an alternative ordering of the composed functions would provide a more efficient execution of makeIndex. Justify your answer. * * * *7) **For the parts 1) to 5) above that you have attempted, discuss the use you have made of a) higher-order functions, b) list comprehension, c) monadic input/output, d) functional composition, and/or e) partial parameterisation (or Curried functions). Include an evaluation of how useful your use of these concepts has been. * * * * * * * *import Prelude* * * *type Doc = String* *type Line = String* *type Word = String * * * *makeIndex :: Doc -> [ ([Int], Word) ]* * * *makeIndex* * = shorten . -- [([Int], Word)] -> [([Int], Word)]* * amalgamate .-- [([Int], Word)] -> [([Int], Word)]* * makeLists . -- [(Int, Word)] -> [([Int], Word)]* * sortLs . -- [(Int, Word)] -> [(Int, Word)]* * allNumWords .-- [(Int, Line)] -> [(Int, Word)]* * numLines . -- [Line] -> [(Int, Line)]* * splitUp -- Doc -> [Line]* * * *splitUp :: Doc -> [Line]* * * *splitUp [] = []* *splitUp text* * = takeWhile (/='\n') text : -- first line* * (splitUp . -- splitup other lines* * dropWhile (==’\n’) . -- delete 1st newline(s)* * dropWhile (/='\n')) text -- other lines* * * *numLines :: [Line] -> [(Int, Line)]* * * *numLines lines -- list of pairs of * * = zip [1 .. length lines] lines -- line no. & line* * * *-- for each line* *-- a) split into words* *-- b) attach line no. to each word* * * *splitWords :: Line -> [Word] -- a)* * * *splitWords [] = []* *splitWords line * * = takeWhile isLetter line : -- first word in line* * (splitWords . -- split other words* * dropWhile (not.isLetter) . -- delete separators* * dropWhile isLetter) line -- other words* * where* * isLetter ch* * = (‘a’<=ch) && (ch<=’z’)* * || (‘A’<=ch) && (ch<=’Z’)* * * *numWords :: (Int, Line) -> [(Int, Word)] -- b)* * * *numWords (number, line)* * = map addLineNum ( splitWords line) -- all line pairs* * where* * addLineNum word = (number, word) -- a pair* * * *allNumWords :: [(Int, Line)] -> [(Int, Word)]* * * *allNumWords = concat . map numWords -- doc pairs * * * *sortLs :: [(Int, Word)] -> [(Int, Word)]* * * *sortLs [ ] = [ ]* *sortLs (a:x)* * = sortLs [b | b <- x, compare b a] -- sort 1st half* * ++ [a] ++ -- 1st in middle* * sortLs [b | b <- x, compare a b] -- sort 2nd half* * where* * compare (n1, w1) (n2, w2)* * = (w1 < w2) -- 1st word less* * || (w1 == w2 && n1 < n2) -- check no. * * * *makeLists :: [(Int, Word)] -> [([Int], Word)]* * * *makeLists * * = map mk -- all pairs* * where mk (num, word) = ([num], word)* * -- list of single no.* * * *amalgamate :: [([Int], Word)] -> [([Int], Word)]* * * *amalgamate [ ] = [ ]* *amalgamate [a] = [a]* *amalgamate ((n1, w1) : (n2, w2) : rest)-- pairs of pairs* * | w1 /= w2 = (n1, w1) : amalgamate ((n2, w2) : rest)* * | otherwise = amalgamate ((n1 ++ n2, w1) : rest)* * -- if words are same grow list of numbers* * * *shorten :: [([Int], Word)] -> [([Int], Word)]* * * *shorten* * = filter long -- keep pairs >4* * where* * long (num, word) = length word > 4 -- check word >4* * *

3 3

Logging in Haskell
by Sergey Mikhanov 30 Mar '09

30 Mar '09

Hi community, As my Haskell programs grow above 100 lines of code, I feel the necessity to trace the execution of them more closely. In imperative languages one may use logging facilities for checking intermediary values of variables, the execution flow, etc. How this usually handled in Haskell (I bet that despite the fact that in Haskell it is relatively easier to write bug-free and checked code, the industrial systems still need some logging being done)? Regards, Sergey

3 2

can run in ghci but can't compile.
by Anand Mitra 30 Mar '09

30 Mar '09

Hi, I can run the following program in the interpreter ghci but can't compile it. The program I am trying to compile is a simple copy using the lazy bytestrings. I have been working out exercises from Real World haskell and I was benchmarking this version which is supposed to be optimum. ,---- | import qualified System as S | import qualified Data.ByteString.Lazy as L | | main = do | [from, to ] <- S.getArgs | file <- L.readFile from | L.writeFile to file `---- While trying to compile this i get the following errors. ,---- | mitra@ravan:~/laptop/haskell/learn$ /opt/ghc-6.10.1/bin/ghc cp.hs | cp.o: In function `sB1_info': | (.text+0xab): undefined reference to `bytestringzm0zi9zi1zi4_DataziByteStringziLazzy_writeFile_closure' | cp.o: In function `sAW_info': | (.text+0xe1): undefined reference to `bytestringzm0zi9zi1zi4_DataziByteStringziLazzy_readFile_closure' | cp.o: In function `sB5_info': | (.text+0x30f): undefined reference to `__stginit_bytestringzm0zi9zi1zi4_DataziByteStringziLazzy_' | cp.o: In function `sB5_srt': | (.data+0x4): undefined reference to `bytestringzm0zi9zi1zi4_DataziByteStringziLazzy_readFile_closure' | cp.o: In function `sB5_srt': | (.data+0x8): undefined reference to `bytestringzm0zi9zi1zi4_DataziByteStringziLazzy_writeFile_closure' | collect2: ld returned 1 exit status | mitra@ravan:~/laptop/haskell/learn$ rm cp.o | mitra@ravan:~/laptop/haskell/learn$ /opt/ghc-6.10.1/bin/ghc cp.hs | cp.o: In function `sB0_info': | (.text+0xab): undefined reference to `bytestringzm0zi9zi1zi4_DataziByteStringziLazzy_writeFile_closure' | cp.o: In function `sAV_info': `---- But this program is not syntactically or otherwise flawed since I can run it under ghci. ,---- | mitra@ravan:~/laptop/haskell/learn$ /opt/ghc-6.10.1/bin/ghci | GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help | Loading package ghc-prim ... linking ... done. | Loading package integer ... linking ... done. | Loading package base ... linking ... done. | Prelude> :l cp.hs | Ok, modules loaded: Main. | Prelude Main> :main /etc/passwd /tmp/xyz | Loading package bytestring-0.9.1.4 ... linking ... done. | Loading package unix-2.3.1.0 ... linking ... done. | Loading package filepath-1.1.0.1 ... linking ... done. | Loading package old-locale-1.0.0.1 ... linking ... done. | Loading package old-time-1.0.0.1 ... linking ... done. | Loading package directory-1.0.0.2 ... linking ... done. | Loading package process-1.0.1.0 ... linking ... done. | Loading package syb ... linking ... done. | Loading package array-0.2.0.0 ... linking ... done. | Loading package random-1.0.0.1 ... linking ... done. | Loading package haskell98 ... linking ... done. | Prelude Main> `---- Since I suspect that this might be a problem with the way I have installed gch-6.10.1 I will explain how I have installed it.

3 3

question from Yet Another Haskell Tutorial
by Michael Mossey 30 Mar '09

30 Mar '09

I have a question about a problem in Yet Another Haskell Tutorial (problem 7.1). My answers seems to disagree with Hal's, and it fact something looks wrong in Hal's answer (maybe it's an error in his paper). The problem is to write the following function in "point-free" style: func5 f list = foldr (\x y -> f(y,x)) 0 list Here's how I approached it. It's easy to drop 'list' by the eta-reduction (using partial application): func5 f = foldr (\x y -> f(y,x)) 0 But how to get rid of f? First I reasoned that f is a function of a tuple. That is, it is not curried. So to curry it: func5 f = foldr (\x y -> (curry f) y x) 0 The second argument to foldr is obviously flipping the arugments, so func5 f = foldr (flip $ curry f) 0 Now I want to use the eta-reduction again, but I have to transform this expression into something that takes f as its last argument instead of the 0. I can use flip again, this time on foldr: func5 f = flip foldr 0 (flip $ curry f) Now f can be dropped: THE FINAL ANSWER: func5 = flip foldr 0 . flip. curry This works, in a couple of my test cases. Now Hal gives this as the answer: func5 = foldr (uncurry $ flip f) 0 The first problem is that there's no argument f, though he refers to it. So maybe he meant func5 f = foldr (uncurry $ flip f) 0 But more problems. He's applying flip to f, but f takes only one argument (a 2-tuple). Then he's uncurry-ing it, but I thought it needed currying, not uncurry-ing. Can anyone figure out what Hal is up to, or does it look like a simple mistake? Thanks, Mike

3 3

numerical types, the $ operator
by TG 30 Mar '09

30 Mar '09

Hi all I'm trying to understand the following simple function >-- | fractional part of number. >frac :: (RealFrac a) => a -> a >frac x = x - fromInteger . floor $ x which apparently is wrong. Whereas this is ok >frac x = x - fromInteger (floor x) Is the 1st one wrong because it is trying to apply the _whole_ 'left of $' to the 'x' on the right? How would an experienced guy write this without parentheses? Moreover, I've put the 'RealFrac' by looking at ":t floor". What kind of class constraint whould you put for doing eg: >frac x = x - fromInteger (floor (sqrt x) ) since 'floor' takes fractional and 'sqrt' takes RealFrac? Some kind of super-class? Thank you. PS Seems that types are half the language, if not more .. -- TG cowscanfly(a)airpost.net -- http://www.fastmail.fm - Access your email from home and the web

6 13