How to make function that split lazy list into two?












0















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









share|improve this question























  • 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
















0















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









share|improve this question























  • 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














0












0








0








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









share|improve this question














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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Nov 25 '18 at 20:37









IlyaIlya

345




345













  • 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

















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












1 Answer
1






active

oldest

votes


















2














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)





share|improve this answer


























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











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
});


}
});














draft saved

draft discarded


















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









2














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)





share|improve this answer


























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
















2














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)





share|improve this answer


























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














2












2








2







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)





share|improve this answer















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)






share|improve this answer














share|improve this answer



share|improve this answer








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



















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

















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




















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Costa Masnaga

Fotorealismo

Sidney Franklin