Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-4041-

Haskell --- average of a list.

Name: Anonymous 2015-07-08 17:53

Rules:

✡ must compute arithmetic average of a list
✡ only one pass is allowed
✡ constant memory

Name: Anonymous 2015-07-08 17:54

The back-story is that some guy in Kyiv asked this question during interviews with about twenty different Haskellers, and not a single one of them was able to solve it correctly.

Name: Anonymous 2015-07-08 17:57

Check this out:

list = [1..1000000000]

sum_ :: [Int] -> Int
sum_ (x:(y:xs)) = (x + y) + sum xs $! (x + y)
sum_ (x:xs) = x + sum xs
sum_ _ = 0

length_ :: [Int] -> Int -> Int
length_ (x:xs) n = length_ xs $! (n + 1) $! (n + 1)
length_ [] n = id $! n

main = do
print "starting"
let fSum = sum_ list
let fLen = length_ list 0

-- Eats a fuckton of memory
--print $ fSum `div` fLen

-- Eats a fuckton of memory. Seriously?
--print fSum
--print fLen

-- Works in constant memory, but it useless.
print $ fSum `div` fSum


I. e. whenever I have two consumers consuming a list, the list is evaluated in full. When I only have one, the list is generated one piece at a time.

What the fuck, GHC?

Name: Anonymous 2015-07-08 18:28

hows this?

(\(y,s) -> y`div`s)) . foldl' (\(tot,len) x -> (tot+x,len+1)) (0,0)

not sure what you mean by "arithmetic average", change div to / if you want

Name: Anonymous 2015-07-08 18:41

U MENA MEAN

Name: Anonymous 2015-07-08 21:27

please rate my post >>4

Name: Anonymous 2015-07-08 21:39

>>4
That's somehow about 1/3 worse than just plain sum/len

Name: Anonymous 2015-07-08 21:40

>>4
pretty good

Name: Anonymous 2015-07-08 22:16

>>4
(\(y,s) -> y`div`s)) ≡ uncurry div

Name: Anonymous 2015-07-09 0:04

>>7
I did that because: ✡ only one pass is allowed

Name: Anonymous 2015-07-09 17:28

<-------------- *** CHECK MY DUBS!!!!!! ***

Name: Anonymous 2015-07-09 18:20

Google interview, eh?

Name: Anonymous 2015-07-10 4:59

Haskell
constant memory
/0

Name: Anonymous 2015-07-10 17:39

{-# LANGUAGE BangPatterns #-}
mean :: (Num a, Fractional a) => [a] -> a
mean xs = go xs 0 0
where go (x:xs) !s !n = go xs (s+x) (n+1)
go [] !s !n = s / n

main = print $ mean [1..3000000]


GHC's profiling tools tell me this uses constant memory.

Name: Anonymous 2015-07-10 18:29

>>13
Why are you dividing that quote by zero?

Name: Anonymous 2015-07-11 12:03

>>15
Who are you dividing by zero?

Name: Anonymous 2015-07-11 12:34

>>16
Whom are you dividing by zero?

Name: Anonymous 2015-07-11 12:43

>>15
-2 = 0-2
+2 = 0+2
*2 = 1*2
/2 = 1/2
/0 = 1/0

Name: Cudder !cXCudderUE 2015-07-12 13:25

Something that is trivial in C, but hilariously difficult in Haskell? I'm not surprised.

Name: Anonymous 2015-07-12 13:29

>>19
uncalled for tbh. sage.

Name: Anonymous 2015-07-12 15:29

avg xs = worker 1 0 xs
where worker _ acc [] = acc
worker n acc (x:xs) = worker (n + 1) (acc * (1 - 1 / n) + x / n) xs

Name: Anonymous 2015-07-12 17:07

<------------------------------------------ check them

Name: Anonymous 2015-07-12 17:52

can we see some fo the failed solutions OP alluded to?

Name: Anonymous 2015-07-12 20:12

>>21
Don't you need to make `acc' strict with a bang pattern to get constant memory usage?

Name: Anonymous 2015-07-12 20:13

>>24
Fuck no. The compiler has had strictness analysis for the last decade at least.

Name: Anonymous 2015-07-12 20:25

>>25
Good point. Just tried compiling it with -O2 and it runs in constant memory.

Name: Anonymous 2015-07-12 23:08

>>21
Holy numerical errors batman!

Name: Anonymous 2015-07-13 16:45

>>27
It's the user's fault for not insisting on bignums. Also, LISP

Name: Anonymous 2015-07-14 0:03

>>19
Any sufficiently complicated Haskell program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of C.

Name: Anonymous 2015-07-14 0:36

Never used Haskell. I use Scheme though, and since TCO's required by the implementation,

(define (average lst)
(let loop ((sum 0) (len 0) (lst lst))
(if (null? lst)
(/ sum len)
(loop (+ (car lst) sum) (+ len 1) (cdr lst)))))


Similar hip functional programming shit though.

Name: Anonymous 2015-07-14 0:47

average list = loop 0 0 lst
where loop sum len [] = sum / len
loop sum len (car:cdr) = loop (car + sum) (len + 1) cdr

Name: Anonymous 2015-07-14 1:11

>>31
Hey, buddy! Check >>33!

Name: Anonymous 2015-07-14 1:22

>>31
is it common for haskell programmers to make heaps of typos? second one I saw in two days

and how come there's so many retarded names in haskell? like they're too lazy to spell "first" and "second", yet they write shit like "putStrLn"

the whole thing looks like it was written by a bunch of camels who forgot how to fuck and are desperately trying to seduce a female camel with symbols, which is probably quite accurate if you replace 'camel' with 'human'.

Name: Anonymous 2015-07-14 10:44

>>33
it's just >>30 with the syntax changed...

Name: Anonymous 2015-07-14 11:13

(defn average [coll] (/ (reduce + coll) (count coll)))

Name: Anonymous 2015-07-14 11:20

>>35
isn't that two passes?

Name: Anonymous 2015-07-14 12:23

>>36
count is O(1) for lists in Clojure

Name: Anonymous 2015-07-14 12:30

>>37
ah, nice

Name: Anonymous 2015-07-14 16:13

>>31
Doesn't pass basic 0-1-∞ testing.

Name: Anonymous 2015-07-15 1:10

>>39
The average of an arbitrary infinite list cannot be computed in general. How can you know what terms arbitrarily far out in the sequence will do in a finite amount of computations without ``knowing'' the sequence symbolically?

Name: Anonymous 2015-07-15 8:47

In perl6:

my $result = [+]@list / @list;

Are you guys even trying?

Name: Anonymous 2015-07-15 8:50

Oops, forgor precedence rules.

( [+] @list ) / @list

This works

Name: Anonymous 2015-07-15 16:52

>>40
Ah but you see, maths is not limited to execution of programs. An inductive argument from the algorithm's formal representation, and another relating it to its implementation, is sufficient to prove correctness of the algorithm and the program code. In practice we'd add tests to an arbitrary (small) subset of ∞, and some tool-driven coverage analysis.

That being said, the weight of that critique is on the case of the zero-element list. One might counter that it's appropriate to leave the average of nothing undefined, but thass' just some sloppy-ass whack right thur as far as pretending to do proper engineering goes.

Name: Anonymous 2015-07-16 6:16

>>43
arbitrary (small) subset
The subset would be small and trivial enough to be impractical to test.

Static typing is a pseudoscience, related to perpetual motion, which is real only in theory

Name: Anonymous 2015-07-16 7:32

It is a truth universally acknowledged that almost all mathematicians are Platonists, at least when they are actually doing mathematics …" This refers to their implicit embrace of essentialism, which he finds revealed in mathematicians peculiar use of language. Whereas physicists define Lie algebra as a rule they can apply to facts, mathematicians define it as an essence of a structure, independent of any circumstance.

Name: Anonymous 2015-07-16 7:48

>>45
This is accurate.

Name: Anonymous 2015-07-16 8:47

It is a truth universally acknowledged that almost all type-theoreticians are Pederasts, at least when they are actually doing type theory …" This refers to their implicit embrace of homosexualism, which he finds revealed in type theory peculiar use of language. Whereas heterosexuals define sex as a rule they can apply to reproduction, type-theoreticians define it as an essence of a structure, independent of any circumstance.

Name: Anonymous 2015-07-16 9:02

>>47
fail. GTFO

Name: Anonymous 2015-07-16 9:05

>>48
Shalom, Hymie!

Name: Anonymous 2015-07-16 12:21

>>47
Kike theory is made up bullshit.
The age-old practice of inventing new unscientific "ideologies" that can change on a whim is still alive and well.

Name: Anonymous 2015-07-18 3:45


Don't change these.
Name: Email:
Entire Thread Thread List