May 2003 - Haskell-Cafe

Re: Random access times
by Ron de Bruijn 10 May '03

10 May '03

I finally succeeded in doing your little exercise :), except for the newArray_. I get the following error: Compiling Try ( try.hs, interpreted ) try.hs:37: Could not deduce (Num i) from the context (MArray IOUArray Foo IO, HasBounds IOUArray, Monad IO, Ix i) Probable fix: Add (Num i) to the class or instance method `newArray_' arising from use of `*' at try.hs:37 In the first argument of `newArray_', namely `(fst (bound), (snd (bound)) * 2)' In a 'do' expression pattern binding: newArray_ (fst (bound), (snd (bound)) * 2) Failed, modules loaded: none. Prelude> newArray_ bound= do newArray_ (fst(bound),snd(bound)*2) I don't really understand why I have to do something with the Numclass. I think it is to be sure of the fact that the the arguments given in the tuple are indextypes of type Num, so the values can always be multiplied using the * operator. How can I make this work and why will it work the way you would say it would work? And why can't I just put the types of the functions just above the definition, just like I do with any other function, is it just because of the fact this is a method of a class? newArray_::(MArray a e m, Ix i) => (i, i) -> m (a i e) newArray_ bound= do newArray_ (fst(bound),snd(bound)) Greets Ron __________________________________ Do you Yahoo!? The New Yahoo! Search - Faster. Easier. Bingo. http://search.yahoo.com

1 0

searching for a substring
by sashan 09 May '03

09 May '03

Hi I've written a function that checks for a substring in a given string. This seems like a common thing to do and was wondering if there is a function that does this in one of the standard modules. stringContains :: String -> String -> Bool stringContains _ [] = True stringContains [] _ = False stringContains (h:t) (h1:t1) = if h == h1 then stringContains t t1 else stringContains t (h1:t1) -- sashan http://sashan.netfirms.com -------------------------------------------------- Brain: Here we are, Pinky--at the dawn of time! Pinky: Narf, Brain. Wake me at the noon of time.

5 5

Re: on termination
by oleg＠pobox.com 08 May '03

08 May '03

Peter Gammie wrote: > What I want: a class of functions that don't all terminate, don't all not > terminate, and furthermore I can tell how a given element of the class > will behave without running it. It must have at least some expressiveness; > this is up for grabs, but it'll have to encompass at least primitive > recursion to be interesting. Let us consider a first-order language of functions defined with the help of addition, multiplication, branching-on-zero, and NPFIX. Functional applications are allowed provided they use the names of previously defined functions. (NPFIX n) is the n-th Church numeral (aka fold) NPFIX n f seed --> f (f ... (f seed)) n times (n>=0) seed otherwise The second argument of NPFIX is the name of a previously defined function (a known name, a functional constant). The domain of our functions consists of integers and a special value 'undefined' (to be called NaN for short). The reduction rules are as usual, with an addition NaN + x -> NaN + x for any x, etc. That is, any operation with NaN leads to non-termination. The language obviously includes every primitive recursive function. There are terminating expressions (any expression that never directly or indirectly mentions NaN always terminates). There are obviously non-terminating functions, such as f(x) = x + NaN. It is also clear that the halting predicate for our language is decidable. Given an expressing, we examine it and the body of all involved functions. If we don't find any NaN, we yield TRUE. If we find a NaN, we "abstractly" interpret our expression. That is, we execute it step by step until we come across a step that tries to add, compare, multiply NaN. At this point we yield FALSE. If our abstract interpreter halts, we yield TRUE. Obviously our abstract interpreter is just the concrete interpreter with one small change. Because any sequence of NaN-free reductions in our language is a sequence of reductions for some primitive recursive function, such sequence must terminate. We're a bit running afoul of the requirement: > I can tell how a given element of the class will behave without > running it but then, a decision procedure must take some 'deciding', so to speak -- if it is non-trivial. We must have a deciding machine. In our example, the deciding machine is the original machine with a slight modification.

1 0

on termination
by Cagdas Ozgenc 08 May '03

08 May '03

Greetings. This may be a little off topic, but I could not get much response from comp.theory, so here it goes: Is it possible to have a programming language that can be used to produce only the programs that terminate, but at the same time decide all recursive languages? Or does such limitation automatically reduce the class of languages that such a programming language decide to primitive-recursive? Perhaps, I couldn't explain it very clearly. I suppose another way of saying this is: Is there a strongly normalizing system that can decide the class of recursive languages? Perhaps something less strong than a Turing Machine, for example deciding all recursive languages but not recognizing any recursively enumerable languages. Thanks

5 12

Re: [Arrays] Random Access Times ?
by Ron de Bruijn 08 May '03

08 May '03

--- Hal Daume III <hdaume(a)ISI.EDU> wrote: > > The one is use is a unboxed and you mean I should > > import the Hugslibrary IOExts, just like in my > code , > > right? > > if you're using arrays of complex values like your > data type, i seriously > doubt you're using unboxed arrays. you will have to > write special > instance methods for them. and yes, you should just > be able to use it as > is. > I really don't have any idea about how to create an instance of that IOArray. The only thing I know about this instance is: instance IOArray bounds myDataType where, but that's nog enough. Can you (again) help me? __________________________________ Do you Yahoo!? The New Yahoo! Search - Faster. Easier. Bingo. http://search.yahoo.com

2 4

Annuity Payment
by sdGrego99＠email.com 07 May '03

07 May '03

http://www.helpu-web.com/annuities/ Here is that great annuity site Frank told me about! http://www.helpu-web.com/annuities/ Thanks, Alan you want out: http://1st-helpu.com/rm.html

1 0

writing a function to build a list of ints from user input
by sashan 06 May '03

06 May '03

I'm trying to write a function that builds a list from user input. This is what I've come up with so far. --a program that makes a list of numbers from user input makeList :: IO [Int] makeList = do s <- getLine if read s /= 0 then return (read s:makeList) else return [] However it fails with the following error: Couldn't match `[a]' against `IO [Int]' Expected type: [a] Inferred type: IO [Int] In the second argument of `(:)', namely `makeList' In the first argument of `return', namely `((read s) : makeList)' It's trying to match a list, [a], with type IO [Int]. This causes it to fail. How do I get around this? -- sashan http://sashan.netfirms.com --------------------------- Brain: Here we are, Pinky--at the dawn of time! Pinky: Narf, Brain. Wake me at the noon of time.

3 4

RE: writing a function to build a list of ints from user input
by Simon Marlow 06 May '03

06 May '03

> On Tue, May 06, 2003 at 05:02:56AM -0500, Galen Menzel wrote: > > > > makeList :: IO [Int] > > makeList = do s <- getLine > > case read s of > > 0 -> return [] > > x -> do xs <- makeList > > return (x:xs) > > > > I changed the if to a case so that (read s) doesn't get > called twice. > > Does the compiler not optimize away identical calls? Or is it > not allowed to, for some reason? Yes, GHC will common up the repeated expression when -O is turned on. > On the other hand, if I write a function like: > > long_list = [1..100000] ++ [1..100000] ++ [1..100000] ++ [1..100000] > > And then run a > > putStr $ unlines $ map show long_list > > I would expect this to take very little memory, which would > mean that the > [1..100000] would need to be calculated four separate times > rather than > being calculated once and stored... Well, this is one of the disadvantages of common sub-expression elimination: you have to store the result of the sub-expression between uses. It is a space/time tradeoff, and in cases like the above, a pretty poor one. But GHC does it anyway, because in most (probably all) of the cases we've seen it is a win. Cheers, Simon

1 0

do expression
by sashan 05 May '03

05 May '03

Hi I'm trying to write a simple program to get user input and execute a function based on the input. The program follows: import IO main = do putStrLn "1) f1" putStrLn "2) f2" choice <- getLine case choice of 1 -> do putStrLn "f1" 2 -> do putStrLn "f2" _ -> do putStrLn "" When compiled with ghc I get the following error: test.hs:8: No instance for (Num String) arising from the pattern `2' at test.hs:8 In a case alternative: 2 -> do putStrLn "f2" In the case expression: case choice of 1 -> do putStrLn "f1" 2 -> do putStrLn "f2" _ -> do putStrLn "" Please can someone explain. Thanks

3 2

Maximum value in a list
by sashan 05 May '03

05 May '03

Hi I was reading through the tutorial Yet Another Haskell Tutorial and doing chapter 3 ex 5, write a function using foldr and max to return the maximum value in a list. I came up with the following that will work for positive numbers. maxInList :: [Int]->Int maxInList [] = 0 maxInList l = foldr max 0 l Is there an identity for the max function? Because currently if the list [-1,-3,-4] is passed to maxInList it will return 0.

4 4