Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[MorleyDev]

If the notion that words in English can have more than one meaning bothers you, or that languages and meanings change, expand or shrink over time, I've got some really bad news about the rest of the language

(Also Dictionary is another name for an Associative Array, yes. Dictionary is used to convey that it's a lookup between a key and a value, like a dictionary is a lookup between a word and it's meaning. Map is used to convey that it maps a key to a value.).

Creating a map from a region is 'map out', like "map out the moon". But 'maps to' in English also has a distinct meaning, which is to express a unidirectional relation between two things: A dictionary maps a word to it's meaning.

[Arx]

You're complaining that "map" doesn't intuitively describe what goes on whilst also suggesting that even "panda" would be better than "lambda" for lambda functions? You're coming off as pretty contrarian.

The term map makes pretty much perfect sense, it's not like someone picked a random word from the dictionary. A map is something that lets you find your way from point A to point B; a mathematical map is a function that lets you find your way from value A to value B, and a computing map/dictionary/hash table is a structure that lets you find your way from value A to value B too. Some of the verbiage that's grown up around it is a bit less obvious, but it's all fundamentally sound.

Do you want people to make up completely new words every time they want to describe something in less than a sentence? Should we just use Chinese? Should we keep a list of all "words and characters with mathematical meaning" and never re-use them?

I feel like if we did that, you'd be complaining that the words we use don't relate to what they're describing.

[Reelya]

I prefer to call the datatype a dictionary, since its little use for holding an actual map.

But "dictionary" is also wrong according to the logic you used before. A dictionary has meant a specific thing to normal people for hundreds of years, now you're using it as a word that means something else. Same "problem" as "map". The map class can store one list of numbers and convert to another list of numbers. That's not what normal, everyday people would call a "dictionary". By that argument, the old log tables they used to print would be called a "dictionary" which is clearly not what normal people would understand.

EDIT: also it seems weird to reject "map" because that's not the common usage then to coin your own term for it that nobody else uses, and say it's better.

[strainer]

Dictionary is already in use as a name for an abstract datatype that is functionally very similar to a c++ style 'map'. Its a unique key of any kind to non-exclusive value store unlike a map which is an area or space with inter-relatable values in it that all link to another area or space which has very similar internal relations (I mean an actual map not the ostensible datatype). I didnt coin dictionary or seriously coin zap and panda theyre just jokey examples. I do think zap could be fine though it has the same wappy ring to it which suited the branding of the 'map reduce' scene, and surely Im not completely alone to relish a world of panda functions? It does feel like a dogmatic response to get the 'seems weird of you to reject things and think up your own alternatives' line.

A map is something that lets you find your way from point A to point B

That is fundamentally an arrow, a link, a way from one thing to another, a key to a value, a value to a location, a here to a there. If someone asks for a map and you just give them a direction, they didnt get what they asked for. Maps are multi dimensional with a strict constraint on the arrangment of the links. This is not true of 'map' datatype or the 'map' operation, its one dimensional and has no constraints on the links arrangement. These are very different conceptual things with only a facile commonality - that they both involve linking.

Not all concepts are any dimensional. An any dimensional map is most formally called a 'manifold' afaict... It could be grand to say "manifold these values by the function" man for short. "man it up with the panda". The resulting sexism could be assuaged by the existence of "man reduce" and "man filter".  ?  ?

[Bumber]

Let's call it a "function" instead. That's what it really is.

[MorleyDev]

Well a map operation in Computer Science is a typically a type of higher-order function that returns a function that transforms some data set. (Higher-order function is the name for a function that takes a function as an input type and returns a function as a return type).

Going back to my point: It doesn't mean map as in paper, it means map as in "map to". A musician with no maths knowledge, when describing reading sheet music, could explain it what they do as "I map the note on the sheet to the strings I need to pluck on the guitar". This is valid and correct english, not mathematical double speak intended to confuse.

Map was chosen as the name for the operation because of "to map to", nothing to do with the physical map except that the physical map is the source of the verbage of "map to" via creating a map being "mapping out the landscape", and language just kinda evolved from there, with the act of going from one thing to another through some process becoming also known as mapping (like going from the physical land to a map), and then that getting shortened down to map and so the grammar rules kicking in made it become "to map to".

English not only allows for these kinda of dual meanings, but is rife with them. I already used several in this post alone so far. Like mean - Depending on context, it could refer to "to convey the meaning of", or could mean that something is "cruel".

For the map HOF, an example implementation of the map operation, albeit an inefficient one, in Javascript may be:

Code: [Select]

function map(transformation) {
      return prev => {
             const output = []
             for(const item of prev) {
                     output.push(transformation(item))
             }
             return output
       }
}

const doubleEveryItem = map(x => x * 2)
console.log(doubleEveryItem([1,2,3]))
// outputs [2, 4, 6]

That's basically what the Array.map in Javascript does, but it's implemented as a member function instead of a HOF. A more efficient approach would be to chain Javascript iterables together so you don't create any intermediate arrays.

The member function on Arrays is currently easier to use and chain, but less flexible. This is why there's a push for Javascript to get a pipeline operator. Would let you write the code as something like:

Code: [Select]

[1,2,3] |> map (x => x * 2) |> (x => console.log(x))
If dealing with iterables you may need to instead write:

Code: [Select]

[1,2,3] |> map (x => x * 2) |> toArrayif you wanted to go back to an array at the end.

For more complex examples, chaining map/filter/reduce is so much easier to follow step-by-step than a for loop. You don't need the intermediate arrays when it's all deferred until that toArray.

Code: [Select]

[1,2,3,4,5]
|> filter (x => x % 2 == 0)
|> map (x => x * 2)
|> flatmap (x => [x, x ** 2])
|> distinct
|> toArray
would result in
filter: throws away 1,3,5
map: doubles 2, 4 to 4, 8
flatmap: expands 4 to 4,16. expands 8 to 8, 64
distinct: throws away one of the 8s, so each item in the set is unique (distinct)
toArray: finalises to an array to 4, 16, 8, 64

Whilst you could write that was one for loop, it's harder to follow what happens step-by-step in comparison.

Code: [Select]

const data = [1,2,3,4,5]
const result = []
for (const item of data) {
    if (item % 2 === 0) {
        const doubled = item * 2
        if (result.indexOf(doubled) === -1) {
            result.push(doubled)
        }
        const doubledSquared = doubled ** 2
        if (result.indexOf(doubledSquared ) === -1) {
            result.push(doubledSquared)
        }
    }
}
Modifying the chain, changing a step, removing a step or adding extra steps, is also easier than with the naked for loop. That's pretty much the motivation behind the existence of map in code.

In theory it would also be possible for a compiler/runtime to automatically make the transformations concurrent without the developer needing to explicitly code that concurrency, but that's more a happy side-benefit of the approach.

[Culise]

Let's call it a "function" instead. That's what it really is.

Problem is that "function" originates, like map, in mathematics.  We'd need to use a different term, lest we confuse the functions of a computer program with its functions.

[MorleyDev]

Plus, a function is a type of 'mapping' in Mathematica, since they map a value onto some other value

Mapping being the source of the verb, to map to, as I explained above. English is a broken language. We took a noun, map, created a more generic noun and verb from it to describe a task, the task of mapping being the act of mapping between two forms such as landscape and paper, then shortened that noun that could also be a verb down to a shorter verb, map to, which contained as one of its parts the original noun.

*Then* mathematica came along and decided that the verb was the best fit for a name to describe things and turned it into *another* noun, distinct in meaning from the original noun.

*Then* Computer Science came along, decided that thing the mathematica called a map, based on the verb based on the verb form of a noun based on another noun, was a great pattern for expressing sequential data transformations... And also someone else in CompSci decided the verb map made a good noun to describe an Associative Array.

So now you can have a map that maps people to their location on a map mapped to the nearest postcode, take all those postcodes and map them to GPS coordinates and put those coordinates down as a pin on a map.

You're welcome, world

It's called a map because it maps, a filter is called a filter because it filters. These are probably some of the most literal names you'll find. English just loves turning verbs into nouns and nouns into verbs. I call it verbing

[strainer]

English is a broken language

Fully agree, Ive just been examining a particular breakage, but it also holds together over time through scrutiny so I dont think its definitely futile to scrutinize the accepted convention.

map as in "map to". A musician with no maths knowledge, when describing reading sheet music, could explain it what they do as "I map the note on the sheet to the strings I need to pluck on the guitar"

I see the phrase "map to" as originating from casual shorthand "use/involves a map to..." A sheet of music is in a way an encoded map (multidimensional with axis of frequency and time, notes as features/values in that space). Its not one dimensional, if we could speak of one dimensional maps then "log tables" could have been also known as "log maps" , slide rules as "slide mappers" but those would be curious and questionable expressions if anyone had ever used them.

*Then* mathematica came along...

For a moment I really thought this meant I could blame Wolfram, but afaict the originating mathematical use of map as a function is one which is, whats it called? sort of bidirectional - all inputs lead to unique outputs and all outputs back to their inputs. I forget the term, its reversable in the same way which given perfect accuracy points in a map lead to points in a space and points in a space lead back to points in a map. So that use had particular technical license for the purposes of communicating theory without waiting around for perfect words to develop. But now we are saying anything that links things maps things not just a musician casually stating the complex connection between details on a score and their execution, now we are saying technically, matematically programmatically anything that links things maps things, an got here by supposing there was never anything distinctly different between maps and other collections of linkages.

you can have a map that maps people to their location on a map mapped to the nearest postcode

Only because its a map. A list of locations doesnt map people to locations because its a _list_, anymore than a map "lists" things to their locations. Sure we can make sense of that being said, but we can recognise the lost sense in it as well.

[strainer]

map: doubles 2, 4 to 4, 8

doubling is mathematically a mapping function because its reversible by halving. Problem with using map in this way in programming is it can do anything to the input, reversible or not. Nothing wrong with `map (x => x % 2)` the word and its character has lost all distinction. We're even told it never really had any.

Anyway, Ill get over it eventually. Its very handy as it is, called whatever. \o/

[Bumber]

For a moment I really thought this meant I could blame Wolfram, but afaict the originating mathematical use of map as a function is one which is, whats it called? sort of bidirectional - all inputs lead to unique outputs and all outputs back to their inputs. I forget the term, its reversable in the same way which given perfect accuracy points in a map lead to points in a space and points in a space lead back to points in a map.

Bijective (one-to-one)?

[MorleyDev]

you can have a map that maps people to their location on a map mapped to the nearest postcode

Only because its a map. A list of locations doesnt map people to locations because its a _list_, anymore than a map "lists" things to their locations. Sure we can make sense of that being said, but we can recognise the lost sense in it as well.

annotated: you can have a map (data structure, synonym for associative array) that maps (verb, used here to mean links, connects or pairs with) people to their location on a map (noun, a representation of a physical location) mapped (verb, used here to mean translated or transformed) to the nearest postcode.

Also realised I forgot to try and explain y-combinators: As I understand it, in the context of Computer Science they're basically a way to refactor the recursion out of a recursive function.

So if you have a recursive function, like a factorial, then you can refactor it so each step of the recursion is instead expressed as

Code: [Select]

function factorial(value, next) {
    if (value <= 1) {
       return 1
    } else {
       return value * next(value - 1, next)
    }
}
console.log( factorial(4, factorial) )

However, by separating factorial(value, next) so it is 'curried', you can express it instead as

Code: [Select]

function factorial(next) {
   return value => {
       if (value <= 1) {
          return 1
       } else {
          return value * next(next)(value - 1)
       }
    }
}

factorial(factorial)(4)

This could then be passed into another function, which binds the next(next) so that you don't need to do that part in the inner function:

Code: [Select]

function Y(f) { return x => f (Y(f))(x) }

function factorial(next) {
   return value => {
       if (value <= 1) {
          return 1
       } else {
          return value * next(value - 1)
       }
    }
}

console.log(Y(factorial)(4))

The benefit of this is since the recursive function is now detached from the act of recursing, we can wrap that function in such a way as to alter it's behaviour. For example, we could memoize it so that if you put an input that has previously been entered is ever encountered again in another call we do not need to recalculate the entire stack.

Code: [Select]

function Y(f) { return x => f (Y(f))(x) }

function factorial(next) {
   return value => {
       if (value <= 1) {
          return 1
       } else {
          return value * next(value - 1)
       }
    }
}

function memo(fn) {
    const table = { }
return next => input => {
        if (table[input] != null) {
            return table[input]
        } else {
    const result = fn(next)(input)
            table[input] = result
        return result
        }
    }
}

const memoizedFactorial = Y(memo(factorial))
console.log(memoizedFactorial(5))
console.log(memoizedFactorial(4))

You could also use have a function that injects logging at each step of the call stack instead:

Code: [Select]

function log(fn) {
    const table = { }
return next => input => {
    const result = fn(next)(input)
            console.log(input, "=>", result)
            return result
    }
}
But the idea is you can transform the input and/or output of a recursive function at each level of the call stack, instead of only the start and end, without modifying that function directly.

It also serves a purpose in mathematical systems where you can't actually use recursion to preserve mathematical state as functions are prohibited from invoking themselves. I believe this use of the Y-combinator primarily applies to simply-typed lambda calculus, which is a form of lambda calculus where every function is guaranteed to resolve. So it doesn't have the halting problem, but is also not turing complete as a result. Nearly all programming languages lack this limitation though.

The implementation of a Y combinator would be different then, a more complicated form than the one above since the one above is a reduction of the full Y-combinator.

[strainer]

Bijective (one-to-one)?

I think so, I found basically 'invertability' discussed here in wp:Inverse function.

Not all functions have an inverse. For a function to have an inverse, each element y ∈ Y must correspond to no more than one x ∈ X; a function f with this property is called one-to-one or an injection. If f −1 is to be a function on Y, then each element y ∈ Y must correspond to some x ∈ X. Functions with this property are called surjections. This property is satisfied by definition if Y is the image (range) of f, but may not hold in a more general context. To be invertible a function must be both an injection and a surjection. Such functions are called bijections. The inverse of an injection f: X → Y that is not a bijection, that is, a function that is not a surjection, is only a partial function on Y, which means that for some y ∈ Y, f −1(y) is undefined. If a function f is invertible, then both it and its inverse function f−1 are bijections.

That article contains a couple of little graphics illustrating how for bijections - "If f maps X to Y, then f −1 maps Y back to X." This mention of 'map' leaves me unperturbed since points on a map link to points in a space, and points in a space link back to their points on the map. The programming term 'map' doesnt have that constraint. It need only be surjective so could be thought of as a shorthand for a "surjection" operation, like: fullnames = rows.surject( x => x.firstname + " " + x.lastname )

Alas, despite how it seems to me most appropriate for "map" to link as maps do, in the article the word map doesn't have that constraint either and is used later without it: " If f: X → Y is any function (not necessarily invertible), the preimage (or inverse image) of an element y ∈ Y is the set of all elements of X that map to y:". Tssk, oh well, my apologies for flogging the idea.

function Y(f) { return x => f ( Y(f) )(x) }

This is neater than I read before yet still taxing to think through. Ive highlighted the function calling itself in its own freakin' definition Seems like you actually grok it MorleyDev, thanks for setting it out.

There is this difference between JS 'var' and 'let' that surprised me and would be relevant to its functional-language features, changing how its code needs to be read: Every time a variable is declared with let it is a fresh instance, which seems straightforward until we look at a loop:

Code: [Select]

for (let c = 1; c < n; c++){
  call_later(
    function() { console.log("c was " + c) }
  )
  // if ( should_adjust(c) ){ do_adjust(c) }
}

If c was declared with 'var', when the console.logs get called later they'll all print c's final value rather than its value at each iteration, because only one instance of a var is created and maintained by the engine. If c is declared with 'let' the JS engine branches a fresh instance of c for every iteration of the loop, so when the console.logs are called they will log c counting as expected from 1 to n. But this could be really heavy in some cases, and the closure function that logs c there, still doesn't log just what c's value was then as it first seems to be. It logs c's value at the end of each iteration, so eg. the last line could alter the logged value, even though it appears after the closure.

This difference would be really preferred by functional programmers, but it seems those hoping that 'let' would be simpler to understand than var didnt get their wish.

[MorleyDev]

Functional types would avoid the for loop anyway

That is a result of an oddity with how they defined a for loops initial variable declaration. Seems weird to me too that

Code: [Select]

for(let i = 0; i < 10; ++i) { } isn't equivalent to

Code: [Select]

(function () {
   let i = 0;
   for (; i < 10; ++i) {
   }
})()
but instead closer to

Code: [Select]

(function () {
   let _i = 0;
   for (; _i < 10; ++_i) {
         let i = _i
         setTimeout(() => console.log(i))
   }
})()That single let i = 0 and it just being incremented each time really does suggest it's a single variable being mutated, not a fresh one each time that is being assigned the previous ones value then mutated.

Code: [Select]

let c = 0
setTimeout(() => console.log("c was " + c), 0)
c = 10

still logs "c was 10", as let-declared variables are still captured by reference. They just decided to define a for loop in a slightly weird way compared to other languages, thinking that the behaviour it resulted in was more intuitive overall.

Though this is a Javascript oddity though, not so much a functional oddity.

let is on the whole a better default than var (and const is best default) since you don't get that awful type hoisting, but for some reason they decided that in a for-loop that let should make a new reference each time.

[MagmaMcFry]

Inspired by strainer's etymological pickiness, I suggest we should just alter all common data types to match the historical meaning of their names:

Elements of a stack should be able to have many neighbors, weighted by the amount of force they apply, as well as data indicating which direction their neighbors are in. They should also have a fall_over method that rearranges the stack using an arbitrary-precision physical tumbling simulation.

A tree should have lots of roots and lots of leaves and include support for tire swings.

A queue should be a thing at the end of an object, useful for keeping bugs away.

A matrix should be... you know what, it's probably better if you google that yourself.