- Beginners - Haskell.org

Learning Haskell: More About Algebraic Data Types
by Manuel M T Chakravarty 08 Aug '16

08 Aug '16

We just published a new chapter in our online Haskell tutorial ”Learning Haskell”: http://learn.hfm.io This seventh chapter expands on algebraic data types by discussing parametric & recursive data types. It also includes a small graphics library to graphically render binary tries as you construct and manipulate them. Happy Learning! Manuel

1 0

Generalised symbolic expressions
by Dmitrij Szamozvancev 07 Aug '16

07 Aug '16

Hello all, I'm learning about data types and type classes and tried implementing a simple symbolic expression evaluator, but generalised for non-numeric data types. data GenExpr a = Atom a | Sum (GenExpr a) (GenExpr a) | Prod (GenExpr a) (GenExpr a) | Neg (GenExpr a) What I am hoping to do is write a general evaluation function which can some GenExp expression and evaluate it. For example, giving it a GenExp Integer would evaluate it according to normal arighmetic, GenExp Bool would be evaluated using Boolean algebra etc. I've declared explicit type classes for types that can be summed, multiplied and negated: class HasSum a where (.+.) :: a -> a -> a class HasProd a where (.*.) :: a -> a -> a class HasNeg a where (.-) :: a -> a instance HasSum Integer where (.+.) = (+) instance HasProd Integer where (.*.) = (*) instance HasNeg Integer where (.-) = negate instance HasSum Bool where (.+.) = (||) instance HasProd Bool where (.*.) = (&&) instance HasNeg Bool where (.-) = not -- Evaluate generalised expression genEval :: (HasSum a, HasProd a, HasNeg a) => GenExpr a -> a genEval (Atom a) = a genEval (Sum ge1 ge2) = genEval ge1 .+. genEval ge2 genEval (Prod ge1 ge2) = genEval ge1 .*. genEval ge2 genEval (Neg ge) = (.-) $ genEval ge However, I would like it to work with types that don't support all three operations, e.g. natural numbers which don't have a negation operation or strings that only have concatenation as addition: instance HasSum Nat where (.+.) = (+) instance HasProd Nat where (.*.) = (*) instance HasSum String where (.+.) = (++) But these wouldn't be suitable inputs for genEval because they don't fulfil all three type constraints. The only solution I can think of is writing separate genEvalNat and genEvalString functions, which kind of defeats the purpose of the generalisation. Is there a more elegant way to solve this problem? Thank you in advance! Dima

2 2

import Control.Lens.Tutorial
by Dan Phillips 04 Aug '16

04 Aug '16

Hi all I'm trying to follow this tutorial about lenses: https://hackage.haskell.org/package/lens-tutorial-1.0.1/docs/Control-Lens-T… Right at the top of the tutorial,it says do this in ghci: import Control.Lens.Tutorial I tried that, but I got an error: "Could not find module `Control.Lens.Tutorial'" So I tried this: D:\Sync\src\tutorials> stack install lens-tutorial Run from outside a project, using implicit global project config Using resolver: lts-6.9 from implicit global project's config file: C:\Users\dan\AppData\Roaming\stack\global-project\stack.yaml lens-tutorial-1.0.1: download lens-tutorial-1.0.1: configure lens-tutorial-1.0.1: build lens-tutorial-1.0.1: copy/register I'm not exactly sure what that did, but it looked promising. However, I still get the same error in ghci as before when I do the import. My question is, what do I need to do to get the import statement working in ghci so I can follow the tutorial? I would be grateful for any guidance. Thanks. Regards Dan Phillips

2 2

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