# Is this a function?

Given a list of (key, value) pairs, determine whether it represents a function, meaning that each key maps to a consistent value. In other words, whenever two entries have equal keys, they must also have equal values. Repeated entries are OK.

For example:

# Not a function: 3 maps to both 1 and 6
[(3,1), (2,5), (3,6)]

# Function: It's OK that (3,5) is listed twice, and that both 6 and 4 both map to 4
[(3,5), (3,5), (6,4), (4,4)]

Input: An ordered sequence of (key, value) pairs using digits 1 to 9. You may not require a particular ordering. You may alternatively take the key list and value list as separate inputs.

Output: A consistent value for functions, and a different consistent value for non-functions.

Test cases: The first 5 inputs are functions, the last 5 are not.

[(3, 5), (3, 5), (6, 4), (4, 4)]
[(9, 4), (1, 4), (2, 4)]
[]
[(1, 1)]
[(1, 2), (2, 1)]

[(3, 1), (2, 5), (3, 6)]
[(1, 2), (2, 1), (5, 2), (1, 2), (2, 5)]
[(8, 8), (8, 8), (8, 9), (8, 9)]
[(1, 2), (1, 3), (1, 4)]
[(1, 2), (1, 3), (2, 3), (2, 4)]

Here they are as two lists of inputs:

[[(3, 5), (3, 5), (6, 4), (4, 4)], [(9, 4), (1, 4), (2, 4)], [], [(1, 1)], [(1, 2), (2, 1)]]
[[(3, 1), (2, 5), (3, 6)], [(1, 2), (2, 1), (5, 2), (1, 2), (2, 5)], [(8, 8), (8, 8), (8, 9), (8, 9)], [(1, 2), (1, 3), (1, 4)], [(1, 2), (1, 3), (2, 3), (2, 4)]]

• surjective function? – Poke May 4 '17 at 20:50
• @Poke It doesn't have to be surjective. – xnor May 4 '17 at 20:54
• Could the input be two lists of equal length, one for keys one for values? – Calvin's Hobbies May 4 '17 at 21:19
• Is it OK for the (key,value) pairs to be reversed, as in (value,key)? I can shave a few bytes off my answer if so. – ymbirtt May 6 '17 at 9:41
• @ymbirtt Yes, you can have the pairs be in either order. – xnor May 6 '17 at 18:22

# Python 2, 34 bytes

lambda x:len(dict(x))==len(set(x))

Try it online!

Creates a Dictionary and a Set from the input and compare their lengths.
Dictionaries can't have duplicated keys, so all the illegal (and repeated) values are removed.

• Python 3, 30 bytes: lambda x:not dict(x).items()^x – Veedrac May 8 '17 at 10:37

f x=and[v==n|(k,v)<-x,(m,n)<-x,k==m]

Try it online!

Outer (->(k,v)) and inner (-> (m,n)) loop over the pairs and whenever k==m, collect the truth value of v==n. Check if all are true.

• You're too quick! :/ – flawr May 4 '17 at 20:59

# Brachylog, 5 4 bytes

dhᵐ≠

Try it online!

Full program. As far as I can tell, the reason that this is beating most other golfing languages is that is a builtin in Brachylog, whereas most of the other golfing languages need to synthesize it.

## Explanation

dhᵐ≠
d     On the list of all unique elements of {the input},
h    take the first element
ᵐ     of each of those elements
≠  and assert that all those elements are different

As a full program, we get true if the assertion succeeds, or false if it fails.

# Pyth, 5 bytes

I'm pretty happy with this one.

{IhM{
implicit input
{  removes duplicate pairs
hM   first element of each pair
{I     checks invariance over deduplication (i.e. checks if no duplicates)

Try it online!

## Retina, 25 bytes

1({\d+,)(\d+}).*\1(?!\2)

Try it online!

Input format is {k,v},{k,v},.... Prints 0 for functions and 1 for non-functions. I could save two bytes by using linefeeds instead of the commas in the input format, but that's messed up.

• I believe it qualifies as "seriously wack," at least from a technical standpoint. – FryAmTheEggman May 4 '17 at 23:07

# Brachylog, 13 bytes

¬{⊇Ċhᵐ=∧Ċtᵐ≠}

Try it online!

### Explanation

¬{          }      It is impossible...
⊇Ċ               ...to find a subset of length 2 of the input...
Ċhᵐ=            ...for which both elements have the same head...
∧           ...and...
Ċtᵐ≠       ...have different tails.
• Can you explain how Ċhᵐ= and Ċtᵐ≠ work? – CalculatorFeline Jun 1 '17 at 4:17
• @CalculatorFeline Uppercase letters are variable names. Ċ is a special variable called Couple which is always preconstrained to be a list of two elements. is a metapredicate which applies the immediatly previous predicate (h - head or t - tail here) to each element of the input (here, Ċ). = and simpl check that their input contains all equal/all different elements. – Fatalize Jun 1 '17 at 15:24

# MATL, 8 bytes

1Z?gs2<A

Inputs are: an array with the values, followed by an array with the keys.

Output is 1 for function, 0 otherswise.

### Explanation

1Z?

Builds a sparse matrix. Initially all entries contain 0; and 1 is added to each entry (i, j) where j and i are the input key, value pairs.

g

The matrix is converted to logical; that is, entries exceeding 1 (corresponding to duplicate key, value pairs) are set to 1.

s

The sum of each column is computed. This is the number of different values for each key.

2<A

A function will have all such sums less than 2.

# R, 33 bytes

This is my version for R. This takes advantage of the ave function. I have allowed for empty input by setting defaults on the key and value parameters. ave is producing a mean of the values for each of the keys. Fortunately this returns the means in the same order as the input values, so a comparison to the input will indicate if there is different values. Returns TRUE if it is a function.

function(k=0,v=0)all(ave(v,k)==v)

Try it online!

# 05AB1E, 119 7 bytes

Saved 2 bytes thanks to kalsowerus.

Ùø¬DÙQ,

Try it online!

Explanation

Ù           # remove duplicates
ø          # zip
¬         # get the first element of the list (keys)
D        # duplicate list of keys
Ù       # remove duplicates in the copy
Q      # compare for equality
,     # explicitly print result
• @Riley: Yep. I'm still quite happy that the special case only ended up a third of the program :P – Emigna May 4 '17 at 21:40
• I think you could save 3 bytes by replacing \)^ with head (¬): TIO – kalsowerus May 12 '17 at 13:32
• @kalsowerus: Unfortunately that breaks for the special case of [] :( – Emigna May 12 '17 at 14:20
• @Enigma Oh it worked because when testing I still had a leftover , at the end. Add that and then it somehow works with []. – kalsowerus May 12 '17 at 14:26
• Updated TIO – kalsowerus May 12 '17 at 14:45

## JavaScript (ES6), 45 38 bytes

Saved 6 bytes thanks to @Neil

a=>a.some(([k,v])=>m[k]-(m[k]=v),m={})

Returns false or true for functions and non-functions, respectively.

This works by constantly subtracting the old value of each function (m[k]) and the new one (m[k]=v, which also stores the new value). Each time, there are three cases:

• If there was no old value, m[k] returns undefined. Subtracting anything from undefined results in NaN, which is falsy.
• If the old value is the same as the new one, m[k]-v results in 0, which is falsy.
• If the old value is different from the new one, m[k]-v results in a non-zero integer, which is truthy.

Therefore, we just have to make sure that m[k]-(m[k]=v) is never truthy.

• Far too long. Use a=>!a.some(([x,y])=>m[x]-(m[x]=y),m=[]). – Neil May 4 '17 at 21:04
• @Neil Dang it, I knew there had to be some way to utilize m[k] being undefined... Thanks! – ETHproductions May 4 '17 at 21:06

## Mathematica, 24 bytes

UnsameQ@@(#&@@@Union@#)&

Explanation: Union deletes duplicated pairs, then #&@@@ gets the first element from each pair (like First/@ but with fewer bytes). If there is any repetition in these first elements, the pairs don't make a function, which we check with UnsameQ.

(This might have the highest density of @ characters in any program I've written…)

• @ density=1/4 – CalculatorFeline Jun 1 '17 at 4:18

# R, 36 33 bytes

function(k,v)any(v[match(k,k)]-v)

Try it online!

anonymous function; returns FALSE for functions and TRUE for not.

This is being beaten by is finally tied with MickyT's answer!!

# Bash + coreutils, 17

sort -u|uniq -dw1

Input is given via STDIN. key and value are Tab separated and each pair is newline-delimited.

sort removes the duplicate key-value pairs. uniq -d only outputs duplicates, and so outputs the empty string in the case of a function, and a non-empty string otherwise - when there are duplicate keys that map to different values.

# 05AB1E, 9 bytes

Code:

ãü-ʒ¬_}}Ë

Explanation:

ã            # Cartesian product with itself
ü-          # Pairwise subtraction
ʒ  }}     # Filter out elements where the following is not true:
¬_       #   Check whether the first digit is 0
Ë    # Check if all equal

Uses the 05AB1E encoding. Try it online!

• Getting to show off ʒ right away I see :) – Emigna May 4 '17 at 21:22
• @Emigna Yeah haha :p, but I already found a bug that causes me to use }} instead of }. – Adnan May 4 '17 at 21:24

# Jelly, 6 bytes

QḢ€µQ⁼

Try it online!

Explanation

QḢ€µQ⁼
Q      - Remove duplicate pairs
Ḣ€    - Retrieve the first element of each pair
µ   - On the output of what came before..
⁼ - Are the following two equal (bit returned)?
Q  - The output with duplicates removed
- (implicit) the output.

Here is an alternate method, also 6 bytes:

QḢ€ṢIẠ

Try it online!

Instead of testing with removing duplicate keys, this sorts () and checks if the difference between terms (I) is all truthy ()

# R, 95 66 bytes

function(k,v)any(sapply(k,function(x){length(unique(v[k==x]))-1}))

Saved 29 bytes thanks to Jarko Dubbeldam.

Anonymous function. Outputs FALSE if a function and TRUE if not (sorry). Takes as arguments a list of keys and a list of values, like so.

> f(c(1,2,5,1,2),c(2,1,2,2,5))
[1] TRUE # not a function

Loops through all keys and grabs the length of the set of unique values for that key. If any of them are > 1, return TRUE.

This is being beaten by MickyT's answer, and also Giuseppe's. upvote one of those.

• Why are you creating a dataframe, only to then reference the vectors you just put into that dataframe? function(k=0,v=0)any(sapply(k,function(x){length(unique(v[k==x]))-1})) should accomplish the same thing. – JAD May 8 '17 at 7:53
• Because I'm still learning! At least one of the other R answers does it more or less like you describe. – BLT May 8 '17 at 14:19
• sorry if I came off a bit harsh :) your submission is a bit different to the other R answers, and if you were to cut out the redundant data.frame, you might be able to compare better. – JAD May 9 '17 at 6:28

# J-uby, 483325 21 bytes

-3 bytes thanks to Jordan!

:size*:==%[:to_h,~:|]

### Explanation

:size*:==%[:to_h,~:|]

(:size * :==) % [:to_h, ~:|]

# transform :% to explicit lambda
->(x){ (:size * :==).(:to_h ^ x, ~:| ^ x)

# apply explicit x to functions
->(x){ (:size * :==).(x.to_h, x|x) }

# expand :* (map over arguments)
->(x){ :==.(:size.(x.to_h), :size.(x|x) }

# simplify symbol calls to method calls
->(x){ x.to_h.size == (x|x).size }

# :| is set union for arrays; x|x just removes duplicates, like :uniq but shorter
->(x){ x.to_h.size == x.uniq.size }

# First Approach, 33 bytes

-[:[]&Hash,:uniq]|:*&:size|:/&:==

This one is longer than the equivalent Ruby solution, but it was fun to make.

Attempt of explanation by transforming to Ruby:

-[:[]&Hash,:uniq]|:*&:size|:/&:==

-[:[] & Hash, :uniq] | (:* & :size) | (:/ & :==)

# turn into explicit lambda
->(x){ (:/ & :==) ^ ((:* & :size) ^ (-[:[] & Hash, :uniq] ^ x)) }

# simplify expressions now that we have an explicit x
->(x){ :== / (:size * [Hash[x], x.uniq]) }

# translate to equivalent Ruby code
->(x) { [Hash[x], x.uniq].map(&:size).reduce(:==) }

# simplify reduce over explicit array
->(x) { Hash[x].size == x.uniq.size }

I could save 2 bytes with a newer version by replacing :uniq with ~:|

# V, 30 bytes

Úç^¨.*©î±$/d ÎwD ç/HdG Íî Ò1lD Try it online! Outputs 1 for functions and nothing for non-functions. # Mathematica, 35 bytes (l=Length)@Union@#==l@<|Rule@@@#|>& Pure function taking a list of ordered pairs as input and returning True or False. Exploits the fact that Union@# deletes repeated ordered pairs, but <|Rule@@@#|> (an association) deletes all but one ordered pair with a particular first element. So we can just compare the Lengths of the two outputs to check whether the input list is a function. # Jelly, 6 bytes nþḄCȦ Try it online! ### How it works nþḄCȦ Main link. Argument: M (n×2 matrix) nþ` Construct the table of (a != b, c != d) with (a, b) and (c, d) in M. Ḅ Unbinary; map (0, 0), (0, 1), (1, 0), (1, 1) to 0, 1, 2, 3 (resp.). C Complement; map each resulting integer x to 1 - x. Ȧ All; test if all resulting integers are non-zero. # CJam, 19 17 bytes Saved 2 bytes thanks to Martin Ender 0l~$2ew{:.=~!&|}/

Outputs 0 for functions and 1 for non-functions.

Try it online!

Explanation

0                     e# Push a 0. We need it for later.
l~                   e# Read and eval a line of input.
$e# Sort it by the keys. 2ew e# Get all consecutive pairs of the sorted list. { e# For each pair of pairs: :.= e# Check if the keys are equal and if the values are equal. ~!& e# Determine if the keys are equal AND the values are not equal. | e# OR with 0. If any pair indicates that the input is not a function, e# this will become 1 (and remain 1), otherwise it will be 0. }/ e# (end block) # APL (Dyalog), 161211 9 bytes (∪≡⊢)⊃¨∘∪ Try it online! ### Explanation ∪ Unique, remove duplicates; (3 5) (3 5) => (3 5) ¨∘ For each element ⊃ Pick the first sub element (3 5) (2 3) => 3 ≡ Check whether the arguments (listed below) are the same ⊢ The right argument ∪ And the right argument with duplicates removed Prints 0 for false and 1 for true • Whoa, you're getting really good. – Adám May 7 '17 at 21:33 # Actually, 4 bytes ╔♂F═ Try it online! Explanation: ╔♂F═ ╔ uniquify (remove duplicate pairs) ♂F take first items in each pair (keys) ═ are all of the keys unique? # brainfuck, 71 bytes ,[[-[->>+<<]+>>],>[[->+<<->]<[<<]>]>[-<+>]<<[->+<]+[-<<]>>,]-[--->+<]>. Try it online! Input is taken as a flat string: for instance, the first test case would be 35356444. To get the representation shown in the original question, simply add a total of six commas to the program at the right points. Output is U for functions and V for non-functions. ### Explanation For any ASCII code point n, f(n) is stored at cell 2n+1. Cells 2n and 2n+2 are working space, and 0, 2, 4, 6, ... 2n-2 are a trail of breadcrumbs to lead back to cell 0. When the input is proven not to be a function, f(0) is set to 1 (among various side effects). , input first key [ start main loop [-[->>+<<]+>>] move to cell 2n, leaving a trail of breadcrumbs , input value corresponding to current key >[ if key already has a value: [->+<<->]< copy existing value, and compare to new value [<<] if values are different, go to cell -2 > go back to cell 2n+1 (or -1 if mismatch) ] >[-<+>] move existing value back to cell 2n+1 (NOP if no existing value, move the 1 from cell 0 to cell -1 if mismatch) <<[->+<] copy new value to cell 2n+1 (NOP if there was already a value) +[-<<]>> follow breadcrumbs back to cell 0 (NOP if mismatch) , input next key ] (if mismatch, cell -2 becomes the next "cell 0", and the next key is also effectively changed by the breadcrumbs left lying around) -[--->+<]>. add 85 to cell 1 and output the result # Perl 6, 38 bytes !*.unique(:as(~*)).repeated(:as(*[0])) Try it # Pyth - 9 8 bytes ql.d{Ql{ Try it It works by removing any repeated pairs first ({Q); then it compares the length of the list to the length of a dictionary created from the list (if the same x value occurs more than once, the dictionary constructor uses only the last one, resulting in the dictionary being shorter than the list) # MATL, 12 bytes iFFvXu1Z)SdA The input is 2-column matrix, where the first column is key and the second is value. Try it online! ### Explanation i % Input: 2-column matrix FFv % Postpend a row with two zeros. This handles the empty case Xu % Unique rows. This removes duplicate (key, value) pairs 1Z) % Select first column, that is, key. We need to check if all % keys surviving at this point are different S % Sort d % Consecutive differences A % Are all values nonzero? # PHP, 49 bytes foreach($_GET as[$x,$y])($$x=$$x??$y)-$y&&die(n);

Prints nothing for functions and n for non-functions.

# CJam, 1411 9 bytes

_&0f=__&=

Try it online!

Takes input as an array of key/value pairs on the stack, returns 1 if the input is a function, and 0 if it's not.

This solution is based on the snippet _&, which de-duplicates an array by taking the set intersection of it with itself. I do this twice, first on the full input (to get rid of any exactly duplicated key/value pairs) and then on just the keys (to see if there are any duplicate keys still left after the first de-duplication).

Here's the full code with comments:

_&           "remove duplicate key/value pairs from input";
0f=        "remove the values, leaving only the keys";
_       "make a copy of the array of keys";
_&     "remove duplicate keys from the copy";
=    "compare the de-duplicated key array with the original";
• Just so you know, e# is the dedicated line comment syntax in CJam. – Esolanging Fruit May 25 '17 at 1:34

# Ruby, 3930 29 Bytes

Thanks to @ValueInk for saving 9 bytes!

->x{Hash[x].size==(x|x).size}

Port of @Rod's Python 2 answer.

• Hash[x] works just as well tbh – Value Ink May 5 '17 at 19:46
• @ValueInk thanks. Not sure why I didn't think about that. – Cyoce May 5 '17 at 21:11