Problem 3 Write a function buckets : ('a -> 'a > bool) -> 'a list -> 'a list list. that partitions a list into equivalence classes. That is, buckets equiv 1st should return a list of lists where each sublist in the result contains equivalent elements, where two elements are considered equivalent if equiv returns true. For example: buckets () [1;2;3;4] = [[1]; [2]; [3];[4]] buckets () [1; 2; 3; 4; 2; 3; 4;3;4] = [[1]; [2; 2]; [3; 3; 3]; [4; 4;4]] buckets (fun x y-> (=) (x mod 3) (y mod 3)) [1; 2; 3; 4; 5; 6] = [[1;4]; [2;5]; [3;6]] The order of the buckets must reflect the order in which the elements appear in the original list. For example, the output of buckets (=) [1;2;3;4] should be [[1]; [2]; [3]; [4]] and not [[2]; [1]; [3]; [4]] or any other permutation. The order of the elements in each bucket must reflect the order in which the elements appear in the original list. For example, the output of buckets (fun x y (=) (x mod 3) (y mod 3)) [1; 2; 3; 4; 5; 6] should be [[1;4]; [2;5]; [3;6]] and not [[4; 1]; [5;2]; [3;6]] or any other permutations. Assume that the comparison function ('a -> 'a -> bool) is commutative, associative and idempotent. Just use lists. Do not use sets or hash tables. List append function @ may come in handy. [1;2;3] @[4; 5; 6] [1; 2; 3; 4; 5; 6].
Problem 3 Write a function buckets : ('a -> 'a > bool) -> 'a list -> 'a list list. that partitions a list into equivalence classes. That is, buckets equiv 1st should return a list of lists where each sublist in the result contains equivalent elements, where two elements are considered equivalent if equiv returns true. For example: buckets () [1;2;3;4] = [[1]; [2]; [3];[4]] buckets () [1; 2; 3; 4; 2; 3; 4;3;4] = [[1]; [2; 2]; [3; 3; 3]; [4; 4;4]] buckets (fun x y-> (=) (x mod 3) (y mod 3)) [1; 2; 3; 4; 5; 6] = [[1;4]; [2;5]; [3;6]] The order of the buckets must reflect the order in which the elements appear in the original list. For example, the output of buckets (=) [1;2;3;4] should be [[1]; [2]; [3]; [4]] and not [[2]; [1]; [3]; [4]] or any other permutation. The order of the elements in each bucket must reflect the order in which the elements appear in the original list. For example, the output of buckets (fun x y (=) (x mod 3) (y mod 3)) [1; 2; 3; 4; 5; 6] should be [[1;4]; [2;5]; [3;6]] and not [[4; 1]; [5;2]; [3;6]] or any other permutations. Assume that the comparison function ('a -> 'a -> bool) is commutative, associative and idempotent. Just use lists. Do not use sets or hash tables. List append function @ may come in handy. [1;2;3] @[4; 5; 6] [1; 2; 3; 4; 5; 6].
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
![Problem 3
In [ ]:
Write a function
buckets : ('a -> 'a -> bool) -> 'a list -> 'a list list
that partitions a list into equivalence classes. That is, buckets equiv 1st should return a list of lists where each sublist in the result contains equivalent
elements, where two elements are considered equivalent if equiv returns true. For example:
buckets (=) [1; 2; 3; 4] = [[1]; [2] ; [3]; [4]]
buckets (=) [1; 2; 3; 4; 2; 3; 4; 3; 4]
buckets (fun x y -> (=) (x mod 3)
[[1;4]; [2;5]; [3; 6]]
The order of the buckets must reflect the order in which the elements appear in the original list. For example, the output of buckets (=) [1;2;3;4]
should be [[1] ; [2] ; [3] ; [4]] and not [[2]; [¹]; [3]; [4]] or any other permutation.
=
The order of the elements in each bucket must reflect the order in which the elements appear in the original list. For example, the output of buckets (fun x
y -> (=) (x mod 3) (y mod 3)) [1; 2; 3; 4; 5; 6] should be [[1;4]; [2;5]; [3;6]] and not [[4;1]; [5;2]; [3;6]] or any other
permutations.
Just use lists. Do not use sets or hash tables.
[[1]; [2; 2]; [3; 3; 3]; [4; 4;4]]
(y mod 3)) [1; 2; 3; 4; 5; 6]
Assume that the comparison function ('a -> 'a -> bool) is commutative, associative and idempotent.
In [] let buckets p 1 =
List append function @ may come in handy. [1;2;3] @ [4;5;6]
(* YOUR CODE HERE *)
assert (buckets (=) [1; 2; 3; 4] [[¹]; [2] ; [3]; [4]]);
assert (buckets (=) [1; 2; 3; 4; 2; 3; 4; 3; 4]
assert (buckets (fun x y -> (=) (x mod 3)
=
=
[1; 2; 3; 4; 5; 6].
[[1]; [2; 2]; [3; 3; 3]; [4; 4; 4]]);
(y mod 3)) [1; 2; 3; 4; 5; 6]
=
[[1;4]; [2;5]; [3; 6]])](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F95a918cc-648a-4ba1-8333-a4ee16085cbc%2Fa249d592-5a7a-4535-846e-dedf407be52a%2Fzbvd9k8_processed.png&w=3840&q=75)
Transcribed Image Text:Problem 3
In [ ]:
Write a function
buckets : ('a -> 'a -> bool) -> 'a list -> 'a list list
that partitions a list into equivalence classes. That is, buckets equiv 1st should return a list of lists where each sublist in the result contains equivalent
elements, where two elements are considered equivalent if equiv returns true. For example:
buckets (=) [1; 2; 3; 4] = [[1]; [2] ; [3]; [4]]
buckets (=) [1; 2; 3; 4; 2; 3; 4; 3; 4]
buckets (fun x y -> (=) (x mod 3)
[[1;4]; [2;5]; [3; 6]]
The order of the buckets must reflect the order in which the elements appear in the original list. For example, the output of buckets (=) [1;2;3;4]
should be [[1] ; [2] ; [3] ; [4]] and not [[2]; [¹]; [3]; [4]] or any other permutation.
=
The order of the elements in each bucket must reflect the order in which the elements appear in the original list. For example, the output of buckets (fun x
y -> (=) (x mod 3) (y mod 3)) [1; 2; 3; 4; 5; 6] should be [[1;4]; [2;5]; [3;6]] and not [[4;1]; [5;2]; [3;6]] or any other
permutations.
Just use lists. Do not use sets or hash tables.
[[1]; [2; 2]; [3; 3; 3]; [4; 4;4]]
(y mod 3)) [1; 2; 3; 4; 5; 6]
Assume that the comparison function ('a -> 'a -> bool) is commutative, associative and idempotent.
In [] let buckets p 1 =
List append function @ may come in handy. [1;2;3] @ [4;5;6]
(* YOUR CODE HERE *)
assert (buckets (=) [1; 2; 3; 4] [[¹]; [2] ; [3]; [4]]);
assert (buckets (=) [1; 2; 3; 4; 2; 3; 4; 3; 4]
assert (buckets (fun x y -> (=) (x mod 3)
=
=
[1; 2; 3; 4; 5; 6].
[[1]; [2; 2]; [3; 3; 3]; [4; 4; 4]]);
(y mod 3)) [1; 2; 3; 4; 5; 6]
=
[[1;4]; [2;5]; [3; 6]])
Expert Solution
Step 1
let buckets (f:'a->'a->bool) (lst:'a list): 'a list list =
let rec find (find_f: 'a->'a->bool)(find_ht: 'a) (find_acc:'a list list):'a list list =
match find_acc with
[]-> [[find_ht]]
| head::tail -> match head with h::_-> if f h find_ht then (find_ht::head)::tail else head::(find f find_ht tail)
in
let rec parse (parse_f: 'a->'a->bool) (parse_lst:'a list) (parse_acc: 'a list list): 'a list list =
match parse_lst with
[] -> parse_acc
| ht::tl -> parse f tl (find f ht parse_acc)
in
match lst with
[]->[]
| ht::tl -> parse f tl [[ht]];;
buckets ( = ) [1;2;3;4];;
buckets ( = ) [1;2;3;4;2;3;4;3;4];;
buckets (fun x y -> ( = ) (x mod 3) (y mod 3) ) [1;2;3;4;5;6];;
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY