Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Are arrays functions?

futhark-lang.org

Post reply on HN
Print view View original

101–110 of 145 posts

Re: Are arrays functions?

#101

Post by geocar »

psychoslave wrote: post #94
geocar wrote: post #81

Earlier quoted context omitted.

The "monograph game" as you put it, is not for mere funsies: We say x+y instead of plus(x,y) because the former is obviously better.

Anything can be credited better for some metric and evaluation scale, and what is obvious to one can be surprising to someone else. x+y is several step away from plus(x,y), one possible path to render this would be: x+y x + y + x y + x , y + ( x , y ) + ( x , y ) +(x,y) plus(x,y) And there are plenty of other options. For example considering method call noted through middot notation: x·+(y) x·plus(y) x·plus y augend·…

> and what is obvious to one can be surprising to someone else.

That is how obvious things work. If you were not surprised that a[i:j] and :[a;i;j] are the same (: a i j) then it is because it was obvious to you, and now that you have had it pointed it out to you, you were able to show all of the different other variants of this thing without even being prompted to, so I think you understand the answer to your question now.

Re: Are arrays functions?

#102

Post by SanjayMehta »

nomel wrote: post #3
SanjayMehta wrote: post #2

Everything is a function. Next question?

For the downvoters, I think giving examples of what's NOT a function would start an interesting conversation, especially if you don't know how it could possibly be interesting!

Waiting for the m word.

Re: Are arrays functions?

#103

Post by Iceland_jack »

This is to say that (length-indexed) "Arrays" are Representable functors[1]. A `Vec n a` is isomorphic to (Fin n -> a), where Fin n = { x :: Nat | x 
  instance pi n. Representable (Vec n) where
    type Rep (Vec n) = Fin n
    index :: Vec n a -> (Fin n -> a)
    index = ..
    tabulate :: (Fin n -> a) -> Vec n a
    tabulate = ..
[1] https://hackage-content.haskell.org/package/adjunctions-4.4....

Re: Are arrays functions?

#105

Post by fanf2 »

BlackFly wrote: post #92

Arrays are syntactic sugar over something that resembles a function, sure. Real signature of an array implementation would be something like V: [0, N] -> T, but that implies you need to statically prove that each index i for V[i] is less than N. So your code would be littered with such guards for dynamic indexing. Also, N itself will be dynamic, so you need some (at least limited) dependent typing on top of this. So…

Functions are partial in most programming languages, so the fact that arrays are best modelled as partial functions (rather than total functions) isn’t a huge obstacle.

Re: Are arrays functions?

#106

Post by twoodfin »

brabel wrote: post #98
tombert wrote: post #73

Earlier quoted context omitted.

I've been watching those Kaze Emanuar videos on his N64 development, and it's always so weird to me when "doing the expensive computation again" is cheaper than "using the precomputed value". I'm not disputing it, he seems to have done a lot of research and testing confirming the results and I have no reason to think he's lying, but it's so utterly counter-intuitive to me.

Doing maths is extremely fast. You need a lot of maths to get to the same amount of time as a single memory access that is not cached in L1 or L2.

And you need to burn even more cycles before you’ve amortized the cost of using a cache line that could have benefitted some other work.

Re: Are arrays functions?

#107

Post by IsTom »

jxf wrote: post #9
nomel wrote: post #3

Earlier quoted context omitted.

For the downvoters, I think giving examples of what's NOT a function would start an interesting conversation, especially if you don't know how it could possibly be interesting!

In the mathematical sense, all functions are relations, but not all relations are functions.

What are relations, if not an indicator function of a cartesian product?

Re: Are arrays functions?

#108

Post by IsTom »

retsibsi wrote: post #31
nomel wrote: post #3

Earlier quoted context omitted.

For the downvoters, I think giving examples of what's NOT a function would start an interesting conversation, especially if you don't know how it could possibly be interesting!

I didn't downvote but I'd be interested to know what the domain is here -- I'm not going to play dumb and be like, 'rocks are not functions', but I'm not sure exactly what class of thing you're asking for examples of.

I think it's just that you can make alternative (to set theory) formalizations of mathematics in terms of functions and in consequence anything that is thinkable of in terms of mathematics (which includes all computation).

Re: Are arrays functions?

#109

Post by Zambyte »

SanjayMehta wrote: post #70
Zambyte wrote: post #8

Earlier quoted context omitted.

Closures and fexprs

Well a closure is a kind of a record with a function hiding inside it and a record is a function which returns its contents. An fexpr is a function.

If you extend the definition of functions to include state, sure, closures are functions. It would be more correct to call them procedures though, which are a superset of functions and operators with side effects.

> An fexpr is a function.

Try to implement a short circuiting logical `and` operator as a function :-)

Re: Are arrays functions?

#110

Post by cionx »

jwarden wrote: post #91
tombert wrote: post #5

I remember I got a little confused when I was first learning TLA+, because what you normally call "functions" are "operators" [1], and what you'd normally call "maps" or "lists" are called "functions". It was odd to me, because it hadn't really occurred to me before that, given infinite memory (and within a mathematical framework), there's fundamentally not necessarily a difference between a "list" and a "function".…

One case where a function is often not substitutable for an array is equality testing. In a language where any two arrays with the same elements in the same order are equal ([1,2] == [1,2]), the same cannot always be true of two equivalent functions. That is because extensionally equality is undecidable for arbitrary functions. Arrays and functions may be mathematically equivalent but on a programming language level…

I don’t understand this argument. Just because functional extensionality is undecidable for arbitrary functions doesn’t mean that it is undecidable for every class of functions.

In the specific situation, let’s say that by an array we mean a finite, ordered list whose entries are indexed by the numbers 0, 1, …, n - 1 for some natural number n. Let’s also say that two arrays are equal if they have the same length and the same value at each position (in other words, they have “the same elements in the same order”).

If we now want to represent a function f as an array arr such that f(i) = arr[i] for every possible input i of f, then this will only be possible for some very specific functions: those whose domain are the set {0, 1, …, n - 1} for some natural number n. But for any two such functions f, g : {0, 1, …, n - 1} → t, their extensional equality is logically equivalent to the equality of the corresponding arrays: you really can check that f and g are extensionally equal by checking that they are represented by equal arrays.

Post reply on HN