Midwest.io 2014 - Demystifying Haskell - Andrew Rademacher
ฝัง
- เผยแพร่เมื่อ 21 พ.ย. 2024
- This talk was given at Midwest.io 2014.
An in-depth examination of the Fibonacci sequence intended to demonstrate the value of Haskell, bust myths about the difficulty of using Haskell and encourage further research and interest in the language.
About the Speaker
Andrew is a software consultant with experience delivering telemarketing, manufacturing and analytic systems to both web and native platforms.
This is a neat primer for people interested in why haskell is useful.
fibs=1:1:zipWith(+)fibs(tail fibs) ... yeah, I like demonstrating that, too. But I think explaining the Either monad and how that can help reduce complexity could help, too. Many think that since Haskell is "mathematical", that means it's good for pure computation. No! (not that it's bad...but that isn't the point of Haskell.) It's about managing complexity. Mathematical abstractions can be extended to control flow, as they are in FRP, and abstracting-away the loops and ifs that would normally appear in most languages yields incredibly composable software. Coding in that style is an unnatural discipline at first, but you get used to it in time.
dang what a killer presentation
Great speaker!!!!
Haskell brings out this sense of purity to me which no other language does, just that PERL is so good with string processing and Matlab with numerical computation that i prefer these for my day job... probably it will change after this presentation :)
Awesome
I particularly liked the part about memoization
I didn't know chris pratt knew haskell
Great speaker and excellent topic...
HaskellMAD
I'm surprise how close this looks to python. One thing I had to search for is why do you use `1 : 1 : [2, 3, 5]` if `++` is the concatenation operator.
In case someone is wondering the same (stackoverflow.com/questions/5649435/syntax-for-list-construction-concatenation), the types of these two functions are different:
(:) :: a -> [a] -> [a]
(++) :: [a] -> [a] -> [a]
So I guess we could have written `[1] ++ [1] ++ [2, 3, 5]` even though that would make no sense since `:` exists.
This was a good intro to Haskell, but there were several advanced functional programming topics (like pattern matching, for instance) that he glossed over. Would have been better with a bit more time to delve into those topics as well.
-- don't bother with the tuple, add directly
fibs = 1 : 1 : (zipWith (+) fibs (tail fibs))
-- factor out application to the argument 'fibs'
fibs = 1 : 1 : (zipWith (+) tail $ fibs)
-- use list append instead of cons because ... you'll see why in a moment
fibs = [1,1] ++ (zipWith (+) tail $ fibs)
-- use an operator section
fibs = ([1,1] ++) (zipWith (+) tail $ fibs)
-- use composition to bring the self-reference of fibs to the top of the syntax tree
fibs = ([1,1]++) . (zipWith (+) tail) $ fibs
-- factor out the self reference so the name of the list isn't needed at all
-- note this can be read almost directly
-- self-referentially produce the list starting 1,1 followed by what you get if you add
-- each from this list to its follower which is in the corresponding point of the list's tail
fibs = fix $ ([1, 1] ++) . (zipWith (+) tail)
This is a valuable technique because you can unit test a sequence and therefore avoid having to debug:
import Data.Function
initial = ([1, 1] ++)
extension = zipWith (+) tail
fibs_step = initial . extension
fibs = fix fibs_step
main = do
let
write :: (Show t) => t -> IO ()
write = putStrLn . show
-- ==.. compares up to two elements of a list
(==..) = (==) `on` take 2
infixr 3 ==..
write $ initial [] == [1,1]
write $ initial [3] == [1,1,3]
write $ initial [3,4] == [1,1,3,4]
write $ extension [0,0] == [0]
write $ extension [0,1] == [1]
write $ extension [1,0] == [1]
write $ extension [1,1] == [2]
write $ extension [2,5] == [7]
write $ extension [2,5,6,4] == [7,11,10]
-- the first 5 cases promise that the 6th is always what we get
-- but they're not a proof, because the 3rd only checks the first two elements, and maybe
-- there are more, but maybe we can't check... although if we're smart we can change
-- take 2 to take 3 and watch what happens to get a clue so we can still avoid debugging
-- but I know the fixed point *always* starts [1,1]
write $ fibs_step [] == initial []
write $ fibs_step [undefined] == initial []
write $ fibs_step [undefined, undefined] ==.. initial []
write $ fibs_step [undefined, undefined, undefined] ==.. initial []
write $ fibs_step undefined ==.. initial []
write $ fibs_step (initial []) == [1,1,2]
write $ fibs_step [1,1,2] == [1,1,2,3]
Tuples are not small lists. In Haskell you can not iterate over the members of a tuple (with standard iteration procedures).
9:55 - no, you don't have random access in tuples (not as in the RA in RAM, anyway), because they're heterogeneous an index operation wouldn't have a known type. They can be destructured easily though; none of the entries are more costly to access, unlike a list.
Random access refers to O(1) look up of any element. Whereas accessing an element in a list is O(n) in the worst case.
Embodiment of Boss.
Really Intresting presentation. :)
thanks. Great presentation.
why do you put comments as //?
Didn't know Seth McFarlane had a brother who'd code.
actually tuple has a limit of 66 afaik
Data type name and a Class name looks identical in haskell code and it was so confusing for me. If you could make them a different color or something that would help me allot. Also the language extensions made it possible to write the same thing in so many ways, it took me a long time to understand a program. So for now I need something like golang not because it is better but because I can understand other peoples code faster.
FichDichInDemArsch Sorry I can't explain it better, I don't think it was because of OOP but when you have a type that consist of other types then the syntax got confusing for me.
I might have an oversimplified interpretation of what I've seen here, but wouldn't [value] ++ list be the same thing as value : list ? It seems odd that an entire operator would be given to save programmers the task of entering a couple of square brackets and plus signs.
Correct.
1) In general, one of the odd things about Haskell IMO is how you're given functions and operators that are trivial modifications of other functions and operators. Like, mapM_ is just void . mapM, forM_ is just flip mapM_, >>> is just flip (.), concat is just join, map is just fmap, etc.
2) However, (:) and (++) both existing isn't that weird. (:) is a data constructor instantiating a singly linked list node, where the first operand is the value and the second is the next node. (++) is concatenation of two lists. This is like other languages where you *would* still find "new Node()" and "List.concat()" as separate things.
Haskell is a truly strongly-typed language. The type of the cons (:) operator is (a -> [a] -> [a] (where a is ANY type)), whereas the type of the concatenation (++) operator is ([a] -> [a] -> [a]). As you can see, these types are fundamentally incompatible. That is why they have different operators.
"...or any of that nonsense" XD
Not to get overly critical, but giving this example as efficiency comparison is not really fair. It shows one strong side of Haskell that could be easily mitigated with using 3 variables as Fibonacci terms along with one variable as index number.
a = 1, b = 1, c = 0; while(index
Your algorithm lacks the features automatically available in haskell though. At the end he showed the ability to sum the list, and haskell's auto memoization of previously computed values made it easy to grab the next value in the series. You can have it both ways in haskell, the full list, or just the last value, without having to code the algorithm with a specific purpose in mind. The haskell language provides this for free, C doesn't, so this is not a valid criticism.
crcaccounts But there is a way to solve this problem without the need of such features. Just selection of best implementation strategy for problem in hand. This is what I wanted to point out, nothing more. You have choice in a lot languages, it does not mean they will perform equally with the exact same algorithm.
I am not pro or against any of these languages, don't even see the merit in talking about comparing them in any way considering how it is the matter of personal taste. If it makes anyone feel better: I like Haskell. Just like I like C or Scheme. I simply don't compare them in general. To me 'C vs Haskell' would be pointless in most cases, seeing how one is intended as minimalistic imperative language and another as general purpose functional language. From my 'pen and paper mathematician first, programmer second' perspective it is about as subjective and context sensitive as you can get.
If anything, lets agree to disagree and move on. Last thing I want (or anybody needs to see) is a highly subjective discussion of needs, features and why X is better then Y.
Takumf Nongivenames I'm not 100% on the behaviour of the JVM but he ran it with -Xms14g which sets the minimum heap size to 14 gigs. So ofcourse it's going to use a bunch of memory.
This video is very dishonest. The computation at the end is only trying to find the 475000th fib. He should be using an iterative algorithm rather than storing all 475000 intermediate values. That's essentially what Haskell does under the hood. Thus some imperative Python would be as follows:
def fib(n):
x, y = 1, 1
for _ in range(1, n):
x, y = y, x + y
return y
Yes, you'll have additional complexity due to big int libraries for languages other than python. But this code is approximately O(1) space in any imperative language, just as the Haskell code is.
we could all learn 'brainfuck' if we wanted to write unreadable code...
Benjamin Kararic Haskell is pretty readable if you understand the syntax.
never gave it a chance rly :p, just got my mind set on something els. if its true that its better for multithreading in the future with more cores i will have to adapt. still now im sticking with the beatiful java :D
Benjamin Kararic Yeah, I understand. Haskell is a very different language from most.