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

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?
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode + RSS -