Project Euler problem 18/67 solver in Haskell


maximumPath :: [[Int]] -> Int
maximumPath tl = head $ foldl (flip reduce) (head rtl) (tail rtl)
  where rtl = reverse tl
        reduce [] b = []
        reduce a [] = []
        reduce (a:as) (b:c:bs) = (a + max b c) : reduce as (c:bs)
        reduce (a:as) [b] = [a + b]

To solve 67 (which is the more interesting one),


trif <- readFile "triangle.txt"
let answer = maximumPath $ map (\l -> map read l) (map words (lines trif))

Not a very interesting problem, is it, though? And I know it goes without saying, but damn, Haskell is ugly.

Damn, that is pretty terse. Good job!

>>2
I don't think it's ugly at all. Maybe it's a bit hard to follow, because it's terse and doesn't have any explanation.

>>1
Why the hell did you define reduce with the arguments going one way, and then call it flipped? Also, does this even work properly with large inputs?

>>5
Because I wrote reduce first, and then noticed that I had to flip the arguments if I wanted to do the folding, so I just put in a flip. You can just manually unflip it if you're so peeved by it.

I'm not sure what you mean by "large inputs", unless you mean interger overflow, in which case it could. If you change "Int" to "Integer", then this should work on any "numbers triangle" you give it.

>>6
I mean long lists. Generally speaking, you should err on the side of strictness when writing a function that reduces a list to a single value.

>>7
Well than you could just change foldl to foldl', but this worked for both examples in Project Euler, which is all I was really aiming for.

Newfags can't do trif.

Can anyone explain the algorithm? I know you have to do something from bottom to top, but I'm not very sure what would solve this. I think I'd write something that transverses the tree backwards and uses backtracking, but I'm convinced there's a more efficient solution.

>>10
It's just a stratamorphism over the noble inert exofunctor realized in terms of a monoidal fold constriction and an orbital reduction. Didn't you learn this for your first or second PhD?

>>11
don't have one

>>12
Ah, so your a PHP programmer.  Of course you wouldn't understand.

>>13

well you are unemployed

>>14
I will, along with my job.

>>15
I will, along with your job.

>>10

      3
    7   4
  2   4   6
8   5   9   3

Starting with the second row, for each node, set the node's value to max(N + L, N + R), where N is the node's value, L is it's left child's value, and R is it's right child's value. The node with 2 would become 10, since 2 + 8 > 2 + 5. Then discard the leafe nodes. Doing this to the entire row, you get this triangle.


      3
    7   4
  10  13  15

Now repeat the process until just one node is left.


      3
    20  19

     23

And now you have your answer. The Haskell code I posted doesn't do this directly, but instead uses a list of lists to represent the triangle. It takes the bottom list and the next-to-bottom list, and then calculates the new bottom list, and then folds that process until done.

Haskell is the Perl of functional languages. And its unusual evaluation semantics make it hard to judge the computational complexity of expressions. Take that, you functional puritain.

>>18
Haskell is the Perl of functional languages.
That's about the dumbest thing I've ever heard.
And its unusual evaluation semantics make it hard to judge the computational complexity of expressions.
Only if you're a moron.

>>18
amb, bitch

>>19

Maybe point-free style is succint. Except that it resists any attempts toward refactoring. Take a point-free-style code and it has to be rewritten with every tiny modification. Then add to that funny precedence rules ("otherwise currying won't work") and it's Perl sans sigils.

Oh, and when you map and reduce shit, you have to pray to the deforestator that it won't cons. Because there's no fucking guarantee. Deforestator has some hardcoded operators built in and that's it. Use anything else and suddenly the code conses like there's no tomorrow.

Also, good luck mixing monad types. Enjoy your AIDS.

>>21
point-free
You do realize point-free is optional, right? And people rarely use it except for composing a bunch of functions to pass the result to a HOF.

funny precedence rules
If precedence confuses you, then you really are a moron.

map and reduce shit
That's a optimization issue. You're gonna judge a language based on a fixable, temporary, compiler specific, optimization issue? Wow, that's not moronic at all.

mixing monad types
Why, you think it's hard? Using transformers is trivial, but if you're put off by the nesting, just write yourself a new monad. Oh, wait, you can't, you're a moron. Sorry, that was insensitive of me.

>>22
s/a opti/an opti/

>>22
Sorry, that was insensitive of me.
I'd go so far as to say it was.... case insensitive.
YEEEEEAAAAAAAHHHHHHH

>>23
s/ a ([aeiou])/ a \\1/g

>>25
Well done, you replaced nothing. Here's one that fucking works:
s/\ba(?=\s*[aeiou])/an/g

>>22

If precedence confuses you, then you really are a moron.

Precedence confuses many people, actually. Which C programmer hasn't been had by the '&' operator's arbitrary precedence? If precedence isn't confusing then why is there a '``' operator for treating an arbitrary binary function as an infix operator?

That's a optimization issue.

Well in an imperative language i can mutate shit instead of praying to the deforestator. And it's not much of a side effect when mutating a fresh sequence.

FIXABLE, temporary, compiler specific, optimization issue?

Well i suppose writing a deforestator that actually works instead of hardcoded support for left/right folds, map, reduce and some other random shit has been put on hiatus until the halting problem is given a positive answer.

Using transformers is trivial, but if you're put off by the nesting, just write yourself a new monad.

I once read a Haskell ebook that made an assertion that lazy evaluation is fucking awesome. Then it showed a program that consisted of a 'main' function being a 'do' expression, with lots of a '<-' sprinkled here and there.

Last two-thirds of the PDF was showing how to appease Hindley-Milner with type declarations using the arrow syntax, which is readable, not at all confusing and elegant since it was written by actual mathematicians and not some John McCarthy, a political science undergrad.

Last time i tried to give a fuck I read some internets "book" about doing shit for "great good".

So again i was treated to some random shit that didn't interest me at all. Instead of showing how to do cool shit with HM like prove that binary trees have the correct structure, it treated me to random inanity.

Then i learned that functions can't be defined from M-x run-haskell (ghci) prompt, only by loading a whole file. And apparently i can't query the "VM" for function's type, because it's a "black box" and "that's the way it's supposed to be". In the fucking interpreter.

C books start on how one can reify low-level data structure to improve space complexity and locality of reference; Lisp books start with how one can smash the state with revolutionary macros; Smalltalk books (probably, never read any) start with how Squeak internals can be redefined at runtime straight from the IDE. Haskell books say that the program is 9000% more correct since the /types/ of expressions are known at compile time; slightly more useful properties can be proven, this time by writing over 9000 arrows.

Oh yeah, some intense shit can be done with static typing, except it's in sequent calculus and not obsolete HM. Go figure.

Haskell's lazy evaluation is a big win and Haskell can be used to do Real Work. Except that a left-pointing-arrow has to be placed before all the terrible thing. Potential side effects include:

- Creating a new file (modifies file system state)
- Reading from a file (advances the pointer of the file descriptor)
- Raising an exception (doesn't return from a function)
- Printing the result on the screen
- Allocating memory (calls mmap(2)/sbrk(2) which is just not cool)
- Calling a function in a non-tail position (allocates a stack frame)
- Evaluating any expression (advances EIP)
- Having the computer turned on (uses electricity)

So as someone said to be good at functional programming one has to create a new universe every time anything is done, to avoid mutating the state. But what if creating a new universe is a side effect as well?

Some argue that it's good to encapsulate impure shit in a ghetto, present a functional interface to the ghetto, and write the rest in functional style. But why all the fucking arrows? And it can be done in any imperative language as well. Perhaps Haskell is a language for college professors who can judge the quality of their students' programs by the number of left-pointing arrows (as opposed to number of bang signs as in Scheme). Morans learn to hate their future corporate job when they grind side effects for a living, on teh JVM.

Lazy evaluation can be implemented trivially for any language with SICP powers. Srsly. Just use a code walker to embed any function application form in a thunk. When it's time to get an actual result, compute the thunks recursively. Can even be made 'eager' with futures. Probably.

Of course sans deforestator, which would fail anyway if fold/map/whatever function couldn't be determined to be used at compile time. When Haskellers write papers on how their deforestator can nao handle right folds, others happily mutate their shit. And when it comes to OOP, they use dataflow-oriented programming thanks to Excel 101 skills they possess.

Srsly, i can't troll the shit out of anyone. frozenvoid could do better. Tiem to sleep nao. Good night /b/.

>>27
tl;dr

>>28
why do you feel the need to tell people this?
strange

>>29
ts;dr

>>27
Which C programmer hasn't been had by the '&' operator's arbitrary precedence?
I haven't, cause I bothered to read the precedence table, like any decent programmer should.

If precedence isn't confusing then why is there a '``' operator for treating an arbitrary binary function as an infix operator?
Because sometimes they look better that way. like in a `mod` b.

Well in an imperative language *wank* *wank* *wank*
If you have issues with functional languages and/or
lazy evaluation, then that's your own fucking problem, now isn't it?

Well i suppose writing a deforestator that actually works instead of hardcoded support for left/right folds, map, reduce and some other random shit has been put on hiatus until the halting problem is given a positive answer.
They're working implicit parallelism into GHC, so fixing dodgy deforastator can wait, for all I care.

near-incoherent, inaccuracy-laden, crazy-ass ramble
Are you even trying to make a point there? Or are you just venting because you're too lazy (lol) and dense to properly learn Haskell and do something useful with it?

(...) Srsly, i can't troll the shit out of anyone. frozenvoid could do better. Tiem to sleep nao. Good night /b/.
FV could masterfully keep people unsure if he was a clever troll or a batshit insane retard. You can't, you're a lazy moron.

>>27
I once read a Haskell ebook that made an assertion that lazy evaluation is fucking awesome. Then it showed a program that consisted of a 'main' function being a 'do' expression, with lots of a '<-' sprinkled here and there.
You're somehow confusing lazy evaluation with functional purity. The IO monad gives you side effects, not strictness. Also, it's the only monad that does this.

Then i learned that functions can't be defined from M-x run-haskell (ghci) prompt, only by loading a whole file.
You heard wrong. It's true that you can't define new types, typeclasses, or modules at the prompt, but you can use let to bind any variable (including functions) and have it shadow previous uses of the same variable name (just put let before your function definition, and replace any significant newlines with semicolons.)

And apparently i can't query the "VM" for function's type, because it's a "black box" and "that's the way it's supposed to be". In the fucking interpreter.
Yeah you can.
Prelude> :t map
map :: (a -> b) -> [a] -> [b]
Like you care anyway.

Oh, and all the other problems you had with Haskell are completely true, and actual showstoppers, and all of the reasons that Haskell will never be used for writing anything but fibs functions, and even there it's useless because imperative languages are better at it.

>>32
Oh, and all the other problems you had with Haskell are completely true, and actual showstoppers, and all of the reasons that Haskell will never be used for writing anything but fibs functions, and even there it's useless because imperative languages are better at it.
Lies. Shameless lies.

>>33
THE FACT THAT YOU NEGLECTED TO ACTUALLY READ MY POST BEFORE YOU RESPONDED IS A SUPERLATIVE EXAMPLE OF YOUR DISREGARD FOR SCIENCE

>>34
That pasta doesn't fit as a reply. I'm assuming it's pasta because it makes no sense in this context.

>>35
The species of copypasta indigenous to Prague are enumerable on one hand. That post is original content, and YOU'RE A RETARDED

>>36
I never said it was indigenous to /prawg/. You're an ^{unoriginal douchebag and a liar}.

S

L

O

W

P

O

K

E

M

O

N

Gotta catch 'em all!

>>1
maximumPath :: [[Int]] -> Int
maximumPath [] = error "Oh no, you called \"maximumPath []\"!"
maximumPath tl = head $ foldl reduce htl ttl
  where htl : ttl = reverse tl
        reduce [b] (a:_) = [a + b]
        reduce (b:c:cs) (a:as) = (a + max b c) : reduce (c:cs) as
        reduce _ _ = []

expand = map (map read . words) . lines

doToFile file = (readFile file >>=) . (print .)

main = doToFile "triangle.txt" $ maximumPath . expand

I got 99 problems but a one from project euler ain't one

>>51
a one

>>51
>>52
HIT ME

>>53
http://www.last.fm/music/MARGATROID

<-- check em dubz