How to make function that split lazy list into two?
I need to make function that split lazy list. For example, [5;6;3;2;1] -> [5;3;1] and [6;2]. Here is syntax of regular lists, but it have to be lazy. Function split by index, odd to first list, even to second. I write function like this, but I don`t know how to add to lazy list new element:
let rec merge list =
let rec mergeHelp list acc = function
| LNil -> failwith "Empty list"
| LCons(x, xf) ->
if (acc mod 2 == 0)
then LCons(x, function() -> mergeHelp (acc+1) (xf())), LCons(LNil, function() -> LNil)
else LCons(LNil, function() -> LNil), LCons(x, function() -> mergeHelp (acc+1) (xf()))
in mergeHelp list 0
;;
function functional-programming ocaml
add a comment |
I need to make function that split lazy list. For example, [5;6;3;2;1] -> [5;3;1] and [6;2]. Here is syntax of regular lists, but it have to be lazy. Function split by index, odd to first list, even to second. I write function like this, but I don`t know how to add to lazy list new element:
let rec merge list =
let rec mergeHelp list acc = function
| LNil -> failwith "Empty list"
| LCons(x, xf) ->
if (acc mod 2 == 0)
then LCons(x, function() -> mergeHelp (acc+1) (xf())), LCons(LNil, function() -> LNil)
else LCons(LNil, function() -> LNil), LCons(x, function() -> mergeHelp (acc+1) (xf()))
in mergeHelp list 0
;;
function functional-programming ocaml
Maybe start by thinking about the slightly simpler problem: how do you implementList.filter
for lazy lists? I.e., write a function that takes a predicate (function returning bool) and a lazy list, and returns a new lazy list containing just the elements for which the predicate is true. The hint is that you don't need to add any elements to any lists to make this work. It's just a filtering operation.
– Jeffrey Scofield
Nov 25 '18 at 20:59
add a comment |
I need to make function that split lazy list. For example, [5;6;3;2;1] -> [5;3;1] and [6;2]. Here is syntax of regular lists, but it have to be lazy. Function split by index, odd to first list, even to second. I write function like this, but I don`t know how to add to lazy list new element:
let rec merge list =
let rec mergeHelp list acc = function
| LNil -> failwith "Empty list"
| LCons(x, xf) ->
if (acc mod 2 == 0)
then LCons(x, function() -> mergeHelp (acc+1) (xf())), LCons(LNil, function() -> LNil)
else LCons(LNil, function() -> LNil), LCons(x, function() -> mergeHelp (acc+1) (xf()))
in mergeHelp list 0
;;
function functional-programming ocaml
I need to make function that split lazy list. For example, [5;6;3;2;1] -> [5;3;1] and [6;2]. Here is syntax of regular lists, but it have to be lazy. Function split by index, odd to first list, even to second. I write function like this, but I don`t know how to add to lazy list new element:
let rec merge list =
let rec mergeHelp list acc = function
| LNil -> failwith "Empty list"
| LCons(x, xf) ->
if (acc mod 2 == 0)
then LCons(x, function() -> mergeHelp (acc+1) (xf())), LCons(LNil, function() -> LNil)
else LCons(LNil, function() -> LNil), LCons(x, function() -> mergeHelp (acc+1) (xf()))
in mergeHelp list 0
;;
function functional-programming ocaml
function functional-programming ocaml
asked Nov 25 '18 at 20:37
IlyaIlya
345
345
Maybe start by thinking about the slightly simpler problem: how do you implementList.filter
for lazy lists? I.e., write a function that takes a predicate (function returning bool) and a lazy list, and returns a new lazy list containing just the elements for which the predicate is true. The hint is that you don't need to add any elements to any lists to make this work. It's just a filtering operation.
– Jeffrey Scofield
Nov 25 '18 at 20:59
add a comment |
Maybe start by thinking about the slightly simpler problem: how do you implementList.filter
for lazy lists? I.e., write a function that takes a predicate (function returning bool) and a lazy list, and returns a new lazy list containing just the elements for which the predicate is true. The hint is that you don't need to add any elements to any lists to make this work. It's just a filtering operation.
– Jeffrey Scofield
Nov 25 '18 at 20:59
Maybe start by thinking about the slightly simpler problem: how do you implement
List.filter
for lazy lists? I.e., write a function that takes a predicate (function returning bool) and a lazy list, and returns a new lazy list containing just the elements for which the predicate is true. The hint is that you don't need to add any elements to any lists to make this work. It's just a filtering operation.– Jeffrey Scofield
Nov 25 '18 at 20:59
Maybe start by thinking about the slightly simpler problem: how do you implement
List.filter
for lazy lists? I.e., write a function that takes a predicate (function returning bool) and a lazy list, and returns a new lazy list containing just the elements for which the predicate is true. The hint is that you don't need to add any elements to any lists to make this work. It's just a filtering operation.– Jeffrey Scofield
Nov 25 '18 at 20:59
add a comment |
1 Answer
1
active
oldest
votes
I don’t know what your lazy list type is but I’m going to assume from your code it looks like:
type 'a t = LNil | LCons of 'a * (unit -> 'a t)
Note that this is different from a more typical lazy list where (unit -> 'a t)
would be 'a t lazy
.
Chances are that the two lists won’t be consumed in the same way they are generated and we won’t want to scan through the input running all the functions once for the odds and again for the evens. So let’s write a function to pair up elements:
let rec pair = function
| LNil -> LNil
| LCons (fst, rest) ->
match rest () with
| LNil -> LCons ((fst, None), const LNil)
| LCons (snd, rest) ->
let later_pairs = lazy (pair rest()) in
LCons ((fst, Some snd), fun () -> Lazy.force later_pairs)
This function has type 'a t -> ('a * 'a option) t
and the key feature that once you have scanned it once, it is cheap to scan again as you do not recommits the elements of the output. The types are a little bit sad because really we are only allowed None
for the second element in the last element of the result but let us live with that and carry on. First we need some trivial utilities:
let rec map f = function
| LNil -> LNil
| LCons (a, r) -> LCons (f a, fun () -> map f (r ()))
let rec filter_map f = function
| LNil -> LNil
| LCons (x, r) ->
let r () = filter_map f (r ()) in
match f x with
| None -> r ()
| Some a -> LCons (a, r)
These have types ('a -> 'b) -> 'a t -> 'b t
and ('a -> 'b option) -> 'a t -> 'b t
and do the least stupid thing one would guess from reading the type signature. We can now implement the function that does what you want:
let unmerge xs =
let pairs = pair xs in
(map (fun (a,_) -> a) pairs, filter_map (fun (_,b) -> b) pairs)
Sorry, that I don not give type of lazy list, it looks like: type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);; Can you explain me from where you take function filter_some and pair, because there no in standard library and I don not see the definition in your answer?
– Ilya
Nov 26 '18 at 7:05
@Ilya sorry. Those were typos.
– Dan Robertson
Nov 26 '18 at 7:06
I make a little change in your code that hint to me terminal. I tried function for: _________pair (LCons(2, function() -> LCons(3, function() -> LCons(4, function() -> LCons(6, function() -> LNil)))));;________ and get the result _________ - : (int * int option) lazyList = LCons ((2, Some 3), <fun>) _________ so isn`t it one lazy list with tuple elements, or this is just representation of two lazy lists?
– Ilya
Nov 26 '18 at 7:48
Yes, that’s what pair does. It breaks up the list into pairs of elements. Thenunmerge
gives two lists.
– Dan Robertson
Nov 26 '18 at 9:32
Ok, I got it. Thanks a lot for help)
– Ilya
Nov 26 '18 at 9:40
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53471717%2fhow-to-make-function-that-split-lazy-list-into-two%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I don’t know what your lazy list type is but I’m going to assume from your code it looks like:
type 'a t = LNil | LCons of 'a * (unit -> 'a t)
Note that this is different from a more typical lazy list where (unit -> 'a t)
would be 'a t lazy
.
Chances are that the two lists won’t be consumed in the same way they are generated and we won’t want to scan through the input running all the functions once for the odds and again for the evens. So let’s write a function to pair up elements:
let rec pair = function
| LNil -> LNil
| LCons (fst, rest) ->
match rest () with
| LNil -> LCons ((fst, None), const LNil)
| LCons (snd, rest) ->
let later_pairs = lazy (pair rest()) in
LCons ((fst, Some snd), fun () -> Lazy.force later_pairs)
This function has type 'a t -> ('a * 'a option) t
and the key feature that once you have scanned it once, it is cheap to scan again as you do not recommits the elements of the output. The types are a little bit sad because really we are only allowed None
for the second element in the last element of the result but let us live with that and carry on. First we need some trivial utilities:
let rec map f = function
| LNil -> LNil
| LCons (a, r) -> LCons (f a, fun () -> map f (r ()))
let rec filter_map f = function
| LNil -> LNil
| LCons (x, r) ->
let r () = filter_map f (r ()) in
match f x with
| None -> r ()
| Some a -> LCons (a, r)
These have types ('a -> 'b) -> 'a t -> 'b t
and ('a -> 'b option) -> 'a t -> 'b t
and do the least stupid thing one would guess from reading the type signature. We can now implement the function that does what you want:
let unmerge xs =
let pairs = pair xs in
(map (fun (a,_) -> a) pairs, filter_map (fun (_,b) -> b) pairs)
Sorry, that I don not give type of lazy list, it looks like: type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);; Can you explain me from where you take function filter_some and pair, because there no in standard library and I don not see the definition in your answer?
– Ilya
Nov 26 '18 at 7:05
@Ilya sorry. Those were typos.
– Dan Robertson
Nov 26 '18 at 7:06
I make a little change in your code that hint to me terminal. I tried function for: _________pair (LCons(2, function() -> LCons(3, function() -> LCons(4, function() -> LCons(6, function() -> LNil)))));;________ and get the result _________ - : (int * int option) lazyList = LCons ((2, Some 3), <fun>) _________ so isn`t it one lazy list with tuple elements, or this is just representation of two lazy lists?
– Ilya
Nov 26 '18 at 7:48
Yes, that’s what pair does. It breaks up the list into pairs of elements. Thenunmerge
gives two lists.
– Dan Robertson
Nov 26 '18 at 9:32
Ok, I got it. Thanks a lot for help)
– Ilya
Nov 26 '18 at 9:40
add a comment |
I don’t know what your lazy list type is but I’m going to assume from your code it looks like:
type 'a t = LNil | LCons of 'a * (unit -> 'a t)
Note that this is different from a more typical lazy list where (unit -> 'a t)
would be 'a t lazy
.
Chances are that the two lists won’t be consumed in the same way they are generated and we won’t want to scan through the input running all the functions once for the odds and again for the evens. So let’s write a function to pair up elements:
let rec pair = function
| LNil -> LNil
| LCons (fst, rest) ->
match rest () with
| LNil -> LCons ((fst, None), const LNil)
| LCons (snd, rest) ->
let later_pairs = lazy (pair rest()) in
LCons ((fst, Some snd), fun () -> Lazy.force later_pairs)
This function has type 'a t -> ('a * 'a option) t
and the key feature that once you have scanned it once, it is cheap to scan again as you do not recommits the elements of the output. The types are a little bit sad because really we are only allowed None
for the second element in the last element of the result but let us live with that and carry on. First we need some trivial utilities:
let rec map f = function
| LNil -> LNil
| LCons (a, r) -> LCons (f a, fun () -> map f (r ()))
let rec filter_map f = function
| LNil -> LNil
| LCons (x, r) ->
let r () = filter_map f (r ()) in
match f x with
| None -> r ()
| Some a -> LCons (a, r)
These have types ('a -> 'b) -> 'a t -> 'b t
and ('a -> 'b option) -> 'a t -> 'b t
and do the least stupid thing one would guess from reading the type signature. We can now implement the function that does what you want:
let unmerge xs =
let pairs = pair xs in
(map (fun (a,_) -> a) pairs, filter_map (fun (_,b) -> b) pairs)
Sorry, that I don not give type of lazy list, it looks like: type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);; Can you explain me from where you take function filter_some and pair, because there no in standard library and I don not see the definition in your answer?
– Ilya
Nov 26 '18 at 7:05
@Ilya sorry. Those were typos.
– Dan Robertson
Nov 26 '18 at 7:06
I make a little change in your code that hint to me terminal. I tried function for: _________pair (LCons(2, function() -> LCons(3, function() -> LCons(4, function() -> LCons(6, function() -> LNil)))));;________ and get the result _________ - : (int * int option) lazyList = LCons ((2, Some 3), <fun>) _________ so isn`t it one lazy list with tuple elements, or this is just representation of two lazy lists?
– Ilya
Nov 26 '18 at 7:48
Yes, that’s what pair does. It breaks up the list into pairs of elements. Thenunmerge
gives two lists.
– Dan Robertson
Nov 26 '18 at 9:32
Ok, I got it. Thanks a lot for help)
– Ilya
Nov 26 '18 at 9:40
add a comment |
I don’t know what your lazy list type is but I’m going to assume from your code it looks like:
type 'a t = LNil | LCons of 'a * (unit -> 'a t)
Note that this is different from a more typical lazy list where (unit -> 'a t)
would be 'a t lazy
.
Chances are that the two lists won’t be consumed in the same way they are generated and we won’t want to scan through the input running all the functions once for the odds and again for the evens. So let’s write a function to pair up elements:
let rec pair = function
| LNil -> LNil
| LCons (fst, rest) ->
match rest () with
| LNil -> LCons ((fst, None), const LNil)
| LCons (snd, rest) ->
let later_pairs = lazy (pair rest()) in
LCons ((fst, Some snd), fun () -> Lazy.force later_pairs)
This function has type 'a t -> ('a * 'a option) t
and the key feature that once you have scanned it once, it is cheap to scan again as you do not recommits the elements of the output. The types are a little bit sad because really we are only allowed None
for the second element in the last element of the result but let us live with that and carry on. First we need some trivial utilities:
let rec map f = function
| LNil -> LNil
| LCons (a, r) -> LCons (f a, fun () -> map f (r ()))
let rec filter_map f = function
| LNil -> LNil
| LCons (x, r) ->
let r () = filter_map f (r ()) in
match f x with
| None -> r ()
| Some a -> LCons (a, r)
These have types ('a -> 'b) -> 'a t -> 'b t
and ('a -> 'b option) -> 'a t -> 'b t
and do the least stupid thing one would guess from reading the type signature. We can now implement the function that does what you want:
let unmerge xs =
let pairs = pair xs in
(map (fun (a,_) -> a) pairs, filter_map (fun (_,b) -> b) pairs)
I don’t know what your lazy list type is but I’m going to assume from your code it looks like:
type 'a t = LNil | LCons of 'a * (unit -> 'a t)
Note that this is different from a more typical lazy list where (unit -> 'a t)
would be 'a t lazy
.
Chances are that the two lists won’t be consumed in the same way they are generated and we won’t want to scan through the input running all the functions once for the odds and again for the evens. So let’s write a function to pair up elements:
let rec pair = function
| LNil -> LNil
| LCons (fst, rest) ->
match rest () with
| LNil -> LCons ((fst, None), const LNil)
| LCons (snd, rest) ->
let later_pairs = lazy (pair rest()) in
LCons ((fst, Some snd), fun () -> Lazy.force later_pairs)
This function has type 'a t -> ('a * 'a option) t
and the key feature that once you have scanned it once, it is cheap to scan again as you do not recommits the elements of the output. The types are a little bit sad because really we are only allowed None
for the second element in the last element of the result but let us live with that and carry on. First we need some trivial utilities:
let rec map f = function
| LNil -> LNil
| LCons (a, r) -> LCons (f a, fun () -> map f (r ()))
let rec filter_map f = function
| LNil -> LNil
| LCons (x, r) ->
let r () = filter_map f (r ()) in
match f x with
| None -> r ()
| Some a -> LCons (a, r)
These have types ('a -> 'b) -> 'a t -> 'b t
and ('a -> 'b option) -> 'a t -> 'b t
and do the least stupid thing one would guess from reading the type signature. We can now implement the function that does what you want:
let unmerge xs =
let pairs = pair xs in
(map (fun (a,_) -> a) pairs, filter_map (fun (_,b) -> b) pairs)
edited Dec 1 '18 at 17:39
kevinji
8,69542952
8,69542952
answered Nov 25 '18 at 22:36
Dan RobertsonDan Robertson
3,433716
3,433716
Sorry, that I don not give type of lazy list, it looks like: type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);; Can you explain me from where you take function filter_some and pair, because there no in standard library and I don not see the definition in your answer?
– Ilya
Nov 26 '18 at 7:05
@Ilya sorry. Those were typos.
– Dan Robertson
Nov 26 '18 at 7:06
I make a little change in your code that hint to me terminal. I tried function for: _________pair (LCons(2, function() -> LCons(3, function() -> LCons(4, function() -> LCons(6, function() -> LNil)))));;________ and get the result _________ - : (int * int option) lazyList = LCons ((2, Some 3), <fun>) _________ so isn`t it one lazy list with tuple elements, or this is just representation of two lazy lists?
– Ilya
Nov 26 '18 at 7:48
Yes, that’s what pair does. It breaks up the list into pairs of elements. Thenunmerge
gives two lists.
– Dan Robertson
Nov 26 '18 at 9:32
Ok, I got it. Thanks a lot for help)
– Ilya
Nov 26 '18 at 9:40
add a comment |
Sorry, that I don not give type of lazy list, it looks like: type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);; Can you explain me from where you take function filter_some and pair, because there no in standard library and I don not see the definition in your answer?
– Ilya
Nov 26 '18 at 7:05
@Ilya sorry. Those were typos.
– Dan Robertson
Nov 26 '18 at 7:06
I make a little change in your code that hint to me terminal. I tried function for: _________pair (LCons(2, function() -> LCons(3, function() -> LCons(4, function() -> LCons(6, function() -> LNil)))));;________ and get the result _________ - : (int * int option) lazyList = LCons ((2, Some 3), <fun>) _________ so isn`t it one lazy list with tuple elements, or this is just representation of two lazy lists?
– Ilya
Nov 26 '18 at 7:48
Yes, that’s what pair does. It breaks up the list into pairs of elements. Thenunmerge
gives two lists.
– Dan Robertson
Nov 26 '18 at 9:32
Ok, I got it. Thanks a lot for help)
– Ilya
Nov 26 '18 at 9:40
Sorry, that I don not give type of lazy list, it looks like: type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);; Can you explain me from where you take function filter_some and pair, because there no in standard library and I don not see the definition in your answer?
– Ilya
Nov 26 '18 at 7:05
Sorry, that I don not give type of lazy list, it looks like: type 'a lazyList = LNil | LCons of 'a * (unit -> 'a lazyList);; Can you explain me from where you take function filter_some and pair, because there no in standard library and I don not see the definition in your answer?
– Ilya
Nov 26 '18 at 7:05
@Ilya sorry. Those were typos.
– Dan Robertson
Nov 26 '18 at 7:06
@Ilya sorry. Those were typos.
– Dan Robertson
Nov 26 '18 at 7:06
I make a little change in your code that hint to me terminal. I tried function for: _________pair (LCons(2, function() -> LCons(3, function() -> LCons(4, function() -> LCons(6, function() -> LNil)))));;________ and get the result _________ - : (int * int option) lazyList = LCons ((2, Some 3), <fun>) _________ so isn`t it one lazy list with tuple elements, or this is just representation of two lazy lists?
– Ilya
Nov 26 '18 at 7:48
I make a little change in your code that hint to me terminal. I tried function for: _________pair (LCons(2, function() -> LCons(3, function() -> LCons(4, function() -> LCons(6, function() -> LNil)))));;________ and get the result _________ - : (int * int option) lazyList = LCons ((2, Some 3), <fun>) _________ so isn`t it one lazy list with tuple elements, or this is just representation of two lazy lists?
– Ilya
Nov 26 '18 at 7:48
Yes, that’s what pair does. It breaks up the list into pairs of elements. Then
unmerge
gives two lists.– Dan Robertson
Nov 26 '18 at 9:32
Yes, that’s what pair does. It breaks up the list into pairs of elements. Then
unmerge
gives two lists.– Dan Robertson
Nov 26 '18 at 9:32
Ok, I got it. Thanks a lot for help)
– Ilya
Nov 26 '18 at 9:40
Ok, I got it. Thanks a lot for help)
– Ilya
Nov 26 '18 at 9:40
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53471717%2fhow-to-make-function-that-split-lazy-list-into-two%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Maybe start by thinking about the slightly simpler problem: how do you implement
List.filter
for lazy lists? I.e., write a function that takes a predicate (function returning bool) and a lazy list, and returns a new lazy list containing just the elements for which the predicate is true. The hint is that you don't need to add any elements to any lists to make this work. It's just a filtering operation.– Jeffrey Scofield
Nov 25 '18 at 20:59