Have things changed in last 3 years? The first solution is now throwing errors like "ambiguous occurrence 'elem') EDIT: looks like 'elem' is overloaded. Changing it to 'element' fixed the issue.
this video is NOT about application. The codes given are just definitions and it is heavily based on describing something very abstract. Please do not waste your time.
Awesome tutorial! However, I'm really not sold on Haskell's error management, it feels like a bad compromise between "errors as data" and "errors as special control flow". I think exceptions are a really bad idea, they go against the spirit of functional programming, they're easy to mishandle, they complexify many situations, they kill kittens, and the world would be better off without them. Your justification for them at 9:55 is that "if the whole runtime is failing, then only exceptions get through". But why? Why couldn't errors be returned as data? Rust manages it, it's definitely possible. IMHO, the main downsides of "errors as data" are: 1) If function f1 calls function f2 which calls function f3, and so on up to function f100, which returns an error that needs to bubble back up to f1, then all the intermediate functions f2 to f99 have a bit of work to do, which exceptions can avoid. But some synctactic sugar can make this as easy as a single character, for example Rust has the ? operator: when f99 calls f100(...)?, if the return value of f100(...) is an error, then f99 immediately returns this error. There's also map_err in case you need to tweak the error before returning it. This makes the pass-through very lightweight, and I actually like the fact that it's explicit. Exceptions can go through unnoticed, which leads to programming errors. 2) If a function h calls multiple functions g1, g2, g3, ..., g100, which may return errors E1, E2, ..., E100 respectively, and if we suppose that function h just wants to let these errors bubble up to the caller, then its error return type will be E1 | E2 | E3 | ... | E100. In Haskell you will have to define a custom data type just for function h, for example `data ErrorH = ErrorH1 E1 | ErrorH2 E2 | ... | ErrorH100 E100`. If another function G may return errrors E2 | E3 | ... | E101, then it will need its own type ErrorG, which will be treated as completely different from ErrorH by the compiler. Sadly, Haskell does not seem to support such "structural sum types" (e.g., as opposed to languages like Typescript, Flow, Elm, ROC, or Julia, which let you use E1 | E2 | E3 as a perfectly valid type). Please correct me if Haskell does have structural sum types, that would be great! Without structural sum types, you have to deal with every possible combination of errors with its own new type. I can see why exceptions are tempting in this context. Note that Rust doesn't support structural sum types either, and therefore you have to use hacky external libraries to work around these difficulties. And this limitation encourages people to bundle all related errors into a single type, like IOError, you lose a lot of granularity. In short, I don't like Rust's error system either. I haven't played with ROC yet, but its error management looks fabulous. There are no exceptions, it's just errors-as-data, with nice synctactic sugar to make passthrough pretty lightweight (+ explicit + flexible), and with structural sum types that are automatically inferred by the compiler, and let you be as granular as you want with your errors, without any typing nightmare, and proper exhaustivity checks to ensure every error is dealt with. Check out this great talk for more details: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-7SidSvJcPd0.html Perhaps Haskell could evolve in that direction too?
Excellent series, thanks so much! Regarding your warning about `seq` at 8:49, I'm not sure exactly *what the risks are* and *what to do* about them? ➤ Risks → If I understand correctly, using `seq` might sometimes degrade performance (speed or RAM usage) because it messes with the compiler's assumptions. That's the only risk, right? Or is there also a risk of compilation or runtime errors? ➤ What to do → Should I use lazy code by default, and if I hit performance issues, first try to turn the compilation optimisations on (which may automatically make things stricter when needed), and if that's not enough, then try using strict code and see if that improves things?
Great series, thanks! 👍 A note for Linux newbies: at 10:20, when you type `USER="Haskell user"`, you are assuming that the `USER` environment variable has already been exported. This only works because this is a pretty standard variable that is usually exported in your system's init scripts. But if you were to use a different variable name, like `GREET_USER`, then you would have to type `export GREET_USER="Haskell user"`, or else the variable would only be visible to the current shell, not to subprocesses like `greet`. This is why you had to type `export USER` at 10:32, after the variable was `unset`. Once a variable is exported, you can change its value without exporting it again, and the updated value will be available to subprocesses. Alternatively, you could set the variable only for the subprocess like this: GREET_USER="Haskell user" ./greet Hope this helps someone.
In the third exercise I understood why you say that Haskell is pure: lagrange :: [(Float, Float)] -> Float -> Float lagrange xs x = sum [y_i * lagrangeBasis xs x_i x | (x_i, y_i) <- xs] where lagrangeBasis xs x_i x = product [lagrangeOne x_i x_j x | (x_j, _) <- xs, x_j /= x_i] lagrangeOne x_i x_j x = (x - x_j) / (x_i - x_j)
I came up with this solution, I hope it's correct I haven't yet found an input for which it isn't. hasPath :: [(Int, Int)] -> Int -> Int -> Bool hasPath [] x y = False hasPath (x:xs) u v | (fst x == u) && (snd x == v) = True | (fst x /= u) = hasPath xs u v | otherwise = hasPath xs u v || hasPath xs (snd x) v wrapper :: [(Int, Int)] -> Int -> Int -> Bool wrapper xs u v = hasPath (xs ++ xs) u v If there are no edges, then there are no routes. If there is at least one edge and its first vertex is the start node and its second vertex is the end node, we're done. If the first vertex isn't the start node, we just skip this edge and try to find the path in the rest of the edges. Otherwise we start a search in the rest of the edges with both the first and second vertex. We also need a wrapper function which just calls into hasPath, except it doubles the edge list, since it might be possible that ignored edges in the beginning might be needed later, in other words we make sure we visit all pairs of edges in both order. Correction: doubling the list is not enough, I think we need to multiply the list by the number of its elements (number of edges).
My solution seems to work, although it's simpler. For directed graphs, the tuple (a,b) indicates the directed edge from a to b. With this in mind, if I can find a road in which I can start from a tuple with a as a source and go to another tuple while updating my source, it is just a matter of time until i find the case in which the tuple (updated_src, dst) is exactly a member of the list. It works with the list of tuples [(1,2),(2,3),(3,2),(3,4)] and returns True if i search for 1 4 and 1 3, but i don't know if it's bulletproof. Thanks for the videos! hasPath::[(Int,Int)] -> Int -> Int -> Bool hasPath [] _ _ = False hasPath (x:xs) src dst | fst x == src && snd x == dst = True | fst x == src && (fst x <= snd x) = hasPath xs (snd x) dst | fst x == src && (fst x >= snd x) = hasPath xs (fst x) dst | otherwise = hasPath xs src dst
@@TheTIM333 came up with that but then when i unpaused he said to specifically use folding and then i sat there and tried only for the actual solution in the video to be horribly unreadable and unconcise
@@shipweck6253 I agree, it is not exactly the most elegant but this cannot be used as an argument against functional programming as using folding was arbitrarily imposed for the purpose of the exercise.
Hi, Now I checked this in ghci. let x = 1 + 1; let y = x + 5, after forcing y to be evaluated by typing y in ghci, :sprint y is still _. Edited: I didn't mentioned the type as Int. Now its working as expected.
hint for understanding the 2D map: the map function itself is passed as an argument to the second map function - we are applying the map function to each element (list) of the 2D list.
Answer #4 is needlessly complex and assumes there's always a path from x to x. I'd use something like this instead: hasPath :: [(Int, Int)] -> Int -> Int -> Bool hasPath [] _ _ = False hasPath [(a, b)] x y = a == x && b == y hasPath (a:xs) x y | x == fst a = hasPath xs (snd a) y | otherwise = hasPath xs x y
I've seen many videos in this series so far and have to congratulate you for the clear explanation style. I've heard about the STM paper before and think I'm now in a position to try to uderstand it. I'll like the refereces to the conceptual sources! Thank you.
My solution of 4 ex: hasPath :: [(Int, Int)] -> Int -> Int -> Bool hasPath array from to | null [x | x <- array, fst x == from] = False | ([x | x <- array, fst x == from] !! 0) == (from, to) = True | otherwise = ( do let from_array = [x | x <- array, fst x == from] let not_from_array = [x | x <- array, not (fst x == from)] let only_snds_from_array = [(snd x) | x <- from_array] let next_depth = [True | x <- only_snds_from_array, hasPath not_from_array x to] if (not (null next_depth)) then True else False ) main :: IO () main = do print (hasPath [(1, 2), (2, 3), (3, 2), (4, 3), (4, 5)] 1 3) So i just loop in checking of all branches, idk about speed of this sh*t, but hey! Im 15 y. o, and i just russian school boy
For doing question 3 with just the stuff discussed, I figured this would work isAsc :: [Int] -> Bool isAsc (x:xs) | null xs = True | x < head xs = isAsc xs | otherwise = False
Thought I'd add my 2 cents here - higher order functions seem to make this counter-intuitive (at least with was super counter intuitive to me) This was completely counter intuitive to me because I thought map . map would result in a function which takes in a list, uses the second map on the list to produce a new one, then uses the first map on the new list to produce an even newer one This isn't the case because map is a higher order function, so with how it gets evaluated, you end up with a map that internally uses a map All the other comments explain that relatively well but imo it'd be hard to call this "analogous" to mathematical composition, it's a lot more general because higher order functions complicate things a lot - as seen with this example You're not saying that you're applying one map on a list then another map on the result of that list, you're saying that you're creating a new function that is a map, which ITSELF uses a map This is a composition of maps which maps a list of a's to a list of b's, then to a list of c's: mapTransitive:: (b -> c) -> (a -> b) -> a -> c mapTransitive f1 f2 = map f1 . map f2 This is a composition of maps which uses a map to map sublists to new lists so that you get a new list: map2D: (b -> c) -> (a -> b) -> a map2D = map . map The biggest difference is the way arguments get applied - that's what changes the outcome, the order matters a lot
could this implementation of exercise 4 be good? Because it looks much simpler hasPath :: [(Int, Int)] -> Int -> Int -> Bool hasPath [] y z = y==z hasPath ((x1, x2):xs) y z = y==z || (hasPath xs y x1 && hasPath xs x2 z) || hasPath xs y z
At 10:00, you say that the tensor product is a functor, but maps objects of C. My understanding is that would be a morphism, not a functor? Or am I misunderstanding
ghci> incr 7 <interactive>:1:6: error: • No instance for (Num PeaNum) arising from the literal ‘7’ • In the first argument of ‘incr’, namely ‘7’ In the expression: incr 7 In an equation for ‘it’: it = incr 7 data PeaNum = Succ PeaNum | Zero incr:: PeaNum -> PeaNum incr = Succ I don't understand what's Wong?
In Haskell you can check the type of an expression using `:t <expr>`. So, e.g. if you try `:t "hello"` it will output "hello" :: String. Now try this with 7. It is a bit less clear in this case but you will see that 7 is a kind of built in num type. Now if you check the type of Zero (i.e. `:t Zero`) you should see `Zero :: PeaNum`. What you have done with the `data` keyword is define a new datatype in Haskell. Your increment function operates on values of type PeaNum, but the built-in num type.
GHCi, version 9.6.3: ghci> elem e [] = False ghci> elem e (x:xs) = (e==x) || (elem e xs) ghci> elem 2 [0,1,2] True ghci> elem 3 [0,1,2] *** Exception: <interactive>:2:1-37: Non-exhaustive patterns in function elem "elem e (x:xs) = if e==x then True else elem e xs" predictively gives the same result
GHCi only saw one line at a time, so you ended up with only the last equation, not the full definition. You can group lines (note how the continued prompt is ghci|): ghci> :{ ghci| elem _ [] = False ghci| elem e (x:xs) = e==x || elem e xs ghci| :}
@@0LoneTech Thank you! No wonder one-liner "elem e (x:xs) | length xs > 0 = (e==x) || (elem e xs) | otherwise = (e==x)" worked fine. But it felt dirty.
Well, yes and no. I don't think any standard function is called app, but $ and $! have the same signature and id is more general. GHC Control.Arrow also has an app function with a different signature. Once combining functions (composition) becomes routine it might surprise you how useful trivial functions are.
I believe modern GHC can sometimes detect recursive patterns that can be substituted for tail recursion and optimized that, but the happening problem makes it impossible to procedurally check if that's possible. As an aside, I'm not sure I like the explanation of this that's given here. When you call a function, memory needs to be allocated to store inputs, local constants, &c. This chunk of memory is called a stack frame. Recursion causes this to happen repeatedly and you can run out of memory easily. With tail-call optimization, you can reuse the stack frame, because all the current call is going to do is immediately return the value returned by the next call. That means we can guarantee none of the values for the current call are needed anymore.
Ex3 + 2 hours and i finally made it work. But i guess not the best way how i did it: lagrange'' :: [(Float, Float)] -> (Float -> Float) lagrange'' xs = (\k -> foldr (\(xi, yi) acc -> acc + yi * foldl (\acc (x, _) -> acc * ((k - x) / (xi - x))) 1 (filter (\(x, _) -> x /= xi) xs)) 0 xs)
*Spoiler to exercise #3; * --start productFold = foldr (\x y -> x*y) 1 sumFold = foldr (\x y -> x+y) 0 lbasis :: [(Float, Float)] -> Float -> Float -> Float lbasis pos xi x = productFold collection where collection = [(x-xj)/(xi-xj) | (xj, _) <- pos, xi /= xj] lfunc :: [(Float, Float)] -> Float -> Float lfunc pos x = sumFold collection where collection = [ yi * (lbasis pos xi x) | (xi, yi) <- pos] main = do print (lfunc pos 2.0) where pos = [(-2.0, -2.0), (-1.0, 4.0), (0.0, 1.0), (4.0, 8.0)] --end {- wow! this formula is done a fair bit in numerical analysis, and doing it by hand supposedly gives a number of engineeringy people big headache -- but turns out it can be expressed in ~18 lines of Haskell code which is absolutely mind-blowing to me. My python version was about 45 lines long. -}
This is why I failed math. I've since concluded that it was the teacher's fault, because I can full well understand and apply quite complex functions, and I now know how to program in several languages. But this? Nah. No thank you. If I can't play with it, then I guess it's not for me.
I liked my Implementation of the elem-Function : elem y xs = not (null [x | x <- xs, x==y]), because I like the list comprehension stuff. For nub, I have an implementation that throws out all later duplicates by remembering a list of everything it went through. that is a help function of course: nubBuild :: (Eq a) => [a] -> [a] -> [a] nubBuild [] ys = [] nubBuild (x:xs) ys | Main.elem x ys = nubBuild xs ys | otherwise = x:(nubBuild xs (x:ys)) so the actual nub is just nub xs = nubBuild xs [] I would love to know a better way to throw out later duplicates, but I have no Ideas. My isAsc is essentially the same thing, but I use list comprehension to check if the remaining list has smaller elements, so quite wastefull it would seem to me. I know I am 4 years late, but hey maybe someone someday will read this
Woah this is AMAZING. Haskell's build tooling has always been a headache for me since i started learning it 1 year ago. Your video is a game changer. I hope this blows up on the algorithm some day.
