# 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)]]


Leaderboard:

var QUESTION_ID=118960,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/118960/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

• surjective function?
– Poke
Commented May 4, 2017 at 20:50
• @Poke It doesn't have to be surjective.
– xnor
Commented May 4, 2017 at 20:54
• Could the input be two lists of equal length, one for keys one for values? Commented May 4, 2017 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. Commented May 6, 2017 at 9:41
• @ymbirtt Yes, you can have the pairs be in either order.
– xnor
Commented May 6, 2017 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 Commented May 8, 2017 at 10:37
• lambda x:len({**x})==len({*x}) Commented Dec 7, 2021 at 20:11

## Haskell, 36 bytes

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! :/ Commented May 4, 2017 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. Commented May 4, 2017 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? Commented Jun 1, 2017 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. Commented Jun 1, 2017 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.

# 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 Commented May 4, 2017 at 21:40
• I think you could save 3 bytes by replacing \)^ with head (¬): TIO Commented May 12, 2017 at 13:32
• @kalsowerus: Unfortunately that breaks for the special case of [] :( Commented May 12, 2017 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 []. Commented May 12, 2017 at 14:26
• Updated TIO Commented May 12, 2017 at 14:45

# 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!

## 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
Commented May 4, 2017 at 21:04
• @Neil Dang it, I knew there had to be some way to utilize m[k] being undefined... Thanks! Commented May 4, 2017 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 Commented Jun 1, 2017 at 4:18

# J-uby, 483325 21 bytes

-3 bytes thanks to Jordan!

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


### Explanation

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

# "readable"
(: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|:/&:==

# "readable"
-[:[] & 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 ~:|

# 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 :) Commented May 4, 2017 at 21:22
• @Emigna Yeah haha :p, but I already found a bug that causes me to use }} instead of }. Commented May 4, 2017 at 21:24

# 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.


# 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 (Ạ)

# 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?


# 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!!

# K (ngn/k), 11 bytes

{r~?r:*'?x}


Try it online!

Port of chunes' factor answer.

## Explanation

{r~?r:*'?x}

{         }     /function
?x      /distinct values
*'        /first value of each
r:          /store in r
r~?            /is distinct?

• -1 byte if you convert it to a train: ~/1?:\*'?: Commented May 4, 2022 at 14:43

Úç^¨.*©î±$/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. # 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
Commented May 7, 2017 at 21:33

# 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
Commented May 8, 2017 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
Commented May 8, 2017 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
Commented May 9, 2017 at 6:28

# 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


# Desmos, 46 bytes

U=L.unique
f(L)=0^{U.length-U.x.unique.length}


Function returning 1 for functions and 0 for non-functions.

Equivalent, but slightly longer:

f(L)=0^{L.unique.length-L.unique.x.unique.length}


Try it on Desmos!

# Factor, 28 bytes

[ members keys all-unique? ]


Try it online!

• members Get the unique elements
• keys Get the keys of an associative array as a sequence
• all-unique? Are they all unique?
             ! { { 1 2 } { 2 1 } { 5 2 } { 1 2 } { 2 5 } }
members      ! { { 1 2 } { 2 1 } { 5 2 } { 2 5 } }
keys         ! { 1 2 5 2 }
all-unique?  ! f


# Julia, 14 bytes

!x=x⊆Dict(x)

Attempt This Online!

# 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)