- Beginners - Haskell.org

Maybe Return?
by Ramnath R Iyer 31 Jul '16

31 Jul '16

Hi all, I'm trying to write a fairly simple program to understand Haskell in practice. I am implementing a simple REPL where I can write some text, and that text can be parsed into a command with arguments. Then, I would like to be able to turn this into a 'plugin' system of sorts, with a module/logic per command. I understand the Text.Parsec library may already provide these things out of the box, but for now, I would prefer to reinvent the wheel. The program below is what I have working right now (very trivial). I want to modify this program, so that the `evaluate input` returns not a String, but a type X that includes information on whether to "continue" and show a prompt after rendering the result, or exit altogether. So the specific questions I have here are: 1. What would be a sensible type signature for X? 2. Assuming X to exist, what is the right way to modify main to use it? My current intuition is to modify the outputStrLn ... loop statements to include an if-then-else, but I'm not sure what the right modification is (all my attempts seemed like imperative programming and failed compilation unsurprisingly). import Evaluator import System.Console.Haskeline main :: IO () main = runInputT defaultSettings loop where loop :: InputT IO () loop = do line <- getInputLine ">> " case line of Nothing -> return () Just "quit" -> return () Just input -> do outputStrLn $ "Executing: " ++ (evaluate input) loop module Evaluator where evaluate :: String -> String evaluate value = value

3 3

time complexity of pattern matching
by Manikanda Krishnan 30 Jul '16

30 Jul '16

I am new to haskell and I have found it extremely interesting and somewhat addictive .I am curious to know about the time complexity of a pattern matching expression . Thanks in advance . :)

2 4

What's an idiomatic Haskell solution to solve the "Maximum Subarray Problem"?
by Dominik Bollmann 17 Jul '16

17 Jul '16

Hi all, I've recently been trying to implement the "maximum subarray problem" from [1] in Haskell. My first, naive solution looked like this: maxSubArray :: [Int] -> [Int] maxSubArray [] = [] maxSubArray [x] = [x] maxSubArray xs@(_:_:_) = maxArr (maxArr maxHd maxTl) (maxCrossingArray hd tl) where (hd,tl) = splitAt (length xs `div` 2) xs maxHd = maxSubArray hd maxTl = maxSubArray tl maxCrossingArray :: [Int] -> [Int] -> [Int] maxCrossingArray hd tl | null hd || null tl = error "maxArrayBetween: hd/tl empty!" maxCrossingArray hd tl = maxHd ++ maxTl where maxHd = reverse . foldr1 maxArr . tail $ inits (reverse hd) -- we need to go from the center leftwards, which is why we -- reverse the list `hd'. maxTl = foldr1 maxArr . tail $ inits tl maxArr :: [Int] -> [Int] -> [Int] maxArr xs ys | sum xs > sum ys = xs | otherwise = ys While I originally thought that this should run in O(n*log n), a closer examination revealed that the (++) as well as maxHd and maxTl computations inside function `maxCrossingArray` are O(n^2), which makes solving one of the provided test cases in [1] infeasible. Hence, I rewrote the above code using Data.Array into the following: data ArraySum = ArraySum { from :: Int , to :: Int , value :: Int } deriving (Eq, Show) instance Ord ArraySum where ArraySum _ _ v1 <= ArraySum _ _ v2 = v1 <= v2 maxSubList :: [Int] -> [Int] maxSubList xs = take (to-from+1) . drop (from-1) $ xs where arr = array (1, length xs) [(i,v) | (i,v) <- zip [1..] xs] ArraySum from to val = findMaxArr (1, length xs) arr findMaxArr :: (Int, Int) -> Array Int Int -> ArraySum findMaxArr (start, end) arr | start > end = error "findMaxArr: start > end" | start == end = ArraySum start end (arr ! start) | otherwise = max (max hd tl) (ArraySum leftIdx rightIdx (leftVal+rightVal)) where mid = (start + end) `div` 2 hd = findMaxArr (start, mid) arr tl = findMaxArr (mid+1, end) arr (leftIdx, leftVal) = snd $ findMax mid [mid-1,mid-2..start] (rightIdx, rightVal) = snd $ findMax (mid+1) [mid+2,mid+3..end] findMax pos = foldl' go ((pos, arr ! pos), (pos, arr ! pos)) go ((currIdx, currSum), (maxIdx, maxSum)) idx | newSum >= maxSum = ((idx, newSum), (idx, newSum)) | otherwise = ((idx, newSum), (maxIdx, maxSum)) where newSum = currSum + (arr ! idx) I believe this runs in O(n*log n) now and is fast enough for the purpose of solving the Hackerrank challenge [1]. However, I feel this second solution is not very idiomatic Haskell code and I would prefer the clarity of the first solution over the second, if somehow I could make it more efficient. Therefore my question: What would be an efficient, yet idiomatic solution to solving the "maximum subarray problem" in Haskell? (Note: I'm aware that this problem can be solved in O(n), but I'm also happy with idiomatic Haskell solutions running in O(n*log n)) Thanks, Dominik. [1] https://www.hackerrank.com/challenges/maxsubarray

2 2

Values vs. Continuations
by martin 16 Jul '16

16 Jul '16

Hello all, a suspended computation in the Continuation Monad is something you can apply a functio to, right? But this holds for ordinary values as well. In fact, some point out that continuations (acutually suspended computations) are almost indistinguishable from values. If that's the case, can somebody please explain what exactly is gained when we turn everything inside-out to get from values to suspended computations?

1 0

Polymorphism
by Ford 11 Jul '16

11 Jul '16

Hello, Why exporting a function doesn't force you to make its inputs derive a typeclass? That would solve all name clashing (just derive also or give different name, because it is obviously too generic). Why can't you overload field accessor via typeclass easily? data Foo = Foo {HasSize => size :: Int} > :t size HasSize a => size a -> Int Why is String not deprecated yet, throwing warning into your face. I think that haskell is really missing some uniformity, there is nothing like AbstractString and AbstractArray (something like java Collections) so a lot of modules introduces its own functions that are just aliases for others. (Even Prelude itself suffers from this - map fmap liftM, pure return...). King regards! Odesláno z BlueMail

1 0

Haskell laziness and data structures.
by OxFord 09 Jul '16

09 Jul '16

Hello, Why is there no default O(1) random access list data structure in haskell (for example clojure has [] vector). I would expect that this kind of data structure is used very often, so you shouldn't need to import one yourself. Is it safe to assume that ' reverse [1, 2, 3, 4, 5] ' is O(1) ? Is it safe to assume that main = x = [1, 2, 3, 4, 5] x = reverse reverse x won't use more space than for the initial [1, 2, 3, 4, 5] list? (No copy of x) Why is array indexeded by ! and list by !!. Shouldn't they be both instances of something like Indexable? King regards, Ford

5 6

How to move nodes in Data.Tree.Zipper
by martin 09 Jul '16

09 Jul '16

Hello all, I've been playing with Data.Tree.Zipper and one of the tasks I set for myself was to move a node to another position. I endet up in a situation, where I no longer have a clear understanding what "moving" means. Data.Tree.Zipper distinguishes between Nodes ("Full") and Space ("Empty"). So I thought to move a nde I need to know the node to be moved ("Full") and the space where it shall be moved to ("Empty") But I need to do two things: (1) remove the node from its original position (2) insert the node at the empty space given. Both operations are supported by D.T.Z, but once I removed the node, I have a new Zipper, while the space given still refers to the original zipper. The new Zipper has no idea where the deleted node shall be inserted and the original empty space doesn't have the node removed. This is not the fault of D.T.Z, but in a way a real-world problem I had been unaware of. With my original idea I could have moved a node to a subspace of itself, which makes no real sense. It appears that giving two zippers to a tree-modifying function is utterly useless when they refer to the same tree and both undergo modifications by the function. What would be a correct way to think about this?

1 0

search function by type
by OxFord 08 Jul '16

08 Jul '16

Hello, is it possible to search for all functions that have concrete type? For example I want to convert [Char] to [Word], but I don't know whether function for that exist. Or I wanna find contructor for SomeSpecialType and I don't know it's name. Can you search those function in GHCI via some command? E.G. GHCi, version 8.0.1: http://www.haskell.org/ghc/ :? for help [}{] :searchtype / :st [Char] -> [Word] Found X match(es): foo1 :: (Char -> Word) -> [Char] -> [Word] foo2 :: [Char] -> [Word] ... [}{] :st SomeSpecialType Found 1 match(es): foo3 :: ... -> .. -> SomeSpecialType King Regards, Ford

3 2

Case vs Guards. I still don't know what is the difference
by Semih Masat 07 Jul '16

07 Jul '16

Hello, I am new to Haskell and trying to learn it with learnyouahaskell.com and Pluralsight Haskell course. And i have a very noob question. I understand that *if .. else* is just a syntactic sugar over *case. *But what about guards then ? Are guards also *case *in different syntax ? Or vice versa ? Like with an example. anyEven nums | (length (removeOdd nums)) > 0 = True | otherwise = False anyEven' nums = case (removeOdd nums) of [] -> False (x:xs) -> True I can do the same thing with both of them. As i understand the only different thing is, with *case *i can manipulate the parameter (like here in the example i used removeOdd) and can use the manipulated parameter to decide what to do after that. So i will not need to use removeOdd function inside the case. ( maybe i will need to use in every guard definition if i choose to use guards ) Is this it? Is this the only difference between them ? And if it is, why haskell needed do implement both of them. Can't we use function like removeOdd before using it on case or guard functions ? Thanks, and sorry if my english is bad. Semih Masat

3 4

Polymorphism ad hoc
by OxFord 06 Jul '16

06 Jul '16

Hello, why does haskell support only parametric polymorphism? Is it because ad hoc p. || multiple dispatch is bad in general? King Regards, Ford

2 1