July 2016 - Beginners

Multiline code in GHCi
by Shishir Srivastava 29 Aug '17

29 Aug '17

Hi, I am trying to run this basic multiline code in GHCi. I am not sure if this is even possible without writing it in a file and compiling it in a traditional way. ------- Prelude> :set +m Prelude> let main1 = do Prelude| a <- readLn Prelude| return a Prelude| Prelude> Prelude> main1 <interactive>:75:1: No instance for (Show (IO b0)) arising from a use of `print' In the first argument of `print', namely `it' In a stmt of an interactive GHCi command: print it ------- Could someone please confirm if the function can be defined and called like this in GHCi or point to where am going wrong. Thanks, Shishir Srivastava

5 9

Learning Monads with 'setjmp' and 'longjmp' like actions
by Michael Roth 30 Aug '16

30 Aug '16

Hi, I'm really trying hard to understand monads but I guess my brain is trapped in the imperative world. Below what I have done so far. But now I would like to implement something like this: do foo (label, jumped) <- setjmp bar longjmp label But I'm stuck. How can I implement 'setjmp' and 'longjmp' with my monad? I'm not able to grasp how can I design 'setjmp' and somehow create a label to use in 'longjmp'. Maybe my monad structure is not appropriate? Code follows: --------------------------------------------------------------- data World = SomeWorld deriving (Eq, Show) data ProgramResult a = Result { world :: World, result :: a } | Continue { world :: World, continue :: Program a } | Stopped { world :: World } newtype Program a = Program { runProgram :: World -> ProgramResult a } runComplete :: Program a -> World -> (World, a) runComplete prg world0 = case runProgram prg world0 of (Result world1 x1) -> (world1, x1) (Continue world1 prg1) -> runComplete prg1 world1 nop :: Program () nop = return () yield :: Program () yield = Program $ \world -> Continue world nop stop :: Program () stop = Program $ \world -> Stopped world instance Functor Program where fmap = liftM instance Applicative Program where pure = return (<*>) = ap instance Monad Program where return x = Program $ \world0 -> Result world0 x ma >>= fb = Program $ \world0 -> case runProgram ma world0 of (Result world1 x1) -> runProgram (fb x1) world1 (Continue world1 prg1) -> Continue world1 (prg1 >>= fb) (Stopped world1) -> Stopped world1

2 1

reading lines with history from bash terminal in OS X
by Dennis Raddle 08 Aug '16

08 Aug '16

I wrote a program first in Windows, where it works as expected, and now I'm using it in OS X and getting undesired behavior. It reads lines from the terminal using the getLine function. In Windows (DOS, actually) the up and down arrows can be used to choose previously entered lines. However, this does not work in bash in OS X. What do I need to get the history available via the arrow keys? D

3 6

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