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


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