Mixing
How can I make non-decreasing list of lists from one list? Without using recursion, using...
This is my idea of the question but I can't correctly type fold_left method.
Example:
nonDecreasing[1;4;3;2;5;6] == [[1;4];[3];[2;5;6]]
let nonDecreasing list =
match list with
| -> help(a, b, c) = b
| h:: -> 2 (*I don't know, "2" is only to compile*)
| h::t -> let help = List.fold_left (fun(prev, lFinal, lTemp) h -> if(h<List.hd(t)) then (List.hd(t), lFinal, h::lTemp) else (List.hd(t), lTemp@lFinal, h::lTemp)) (h, , ) list ;;
I can't make it properly. I don't know what I do wrong with fold-left function.
ocaml foldleft
asked Nov 21 '18 at 18:07
aagiaagi
42
add a comment |
This is my idea of the question but I can't correctly type fold_left method.
Example:
nonDecreasing[1;4;3;2;5;6] == [[1;4];[3];[2;5;6]]
let nonDecreasing list =
match list with
| -> help(a, b, c) = b
| h:: -> 2 (*I don't know, "2" is only to compile*)
| h::t -> let help = List.fold_left (fun(prev, lFinal, lTemp) h -> if(h<List.hd(t)) then (List.hd(t), lFinal, h::lTemp) else (List.hd(t), lTemp@lFinal, h::lTemp)) (h, , ) list ;;
I can't make it properly. I don't know what I do wrong with fold-left function.
ocaml foldleft
asked Nov 21 '18 at 18:07
aagiaagi
42
6
Could you explain what your code is doing, what specific problem you're struggling with and preferably also format your code so it's all visible on one screen. You're more likely to get a good answer if you make it easy for us to understand what you're actually asking.
– glennsl
Nov 21 '18 at 18:33
add a comment |
This is my idea of the question but I can't correctly type fold_left method.
Example:
nonDecreasing[1;4;3;2;5;6] == [[1;4];[3];[2;5;6]]
let nonDecreasing list =
match list with
| -> help(a, b, c) = b
| h:: -> 2 (*I don't know, "2" is only to compile*)
| h::t -> let help = List.fold_left (fun(prev, lFinal, lTemp) h -> if(h<List.hd(t)) then (List.hd(t), lFinal, h::lTemp) else (List.hd(t), lTemp@lFinal, h::lTemp)) (h, , ) list ;;
I can't make it properly. I don't know what I do wrong with fold-left function.
ocaml foldleft
asked Nov 21 '18 at 18:07
aagiaagi
42
This is my idea of the question but I can't correctly type fold_left method.
Example:
nonDecreasing[1;4;3;2;5;6] == [[1;4];[3];[2;5;6]]
let nonDecreasing list =
match list with
| -> help(a, b, c) = b
| h:: -> 2 (*I don't know, "2" is only to compile*)
| h::t -> let help = List.fold_left (fun(prev, lFinal, lTemp) h -> if(h<List.hd(t)) then (List.hd(t), lFinal, h::lTemp) else (List.hd(t), lTemp@lFinal, h::lTemp)) (h, , ) list ;;
I can't make it properly. I don't know what I do wrong with fold-left function.
ocaml foldleft
ocaml foldleft
asked Nov 21 '18 at 18:07
aagiaagi
42
asked Nov 21 '18 at 18:07
aagiaagi
42
edited Nov 21 '18 at 18:41
aagi
asked Nov 21 '18 at 18:07
aagiaagi
42
asked Nov 21 '18 at 18:07
aagiaagi
42
asked Nov 21 '18 at 18:07
aagiaagi
42
42
6
Could you explain what your code is doing, what specific problem you're struggling with and preferably also format your code so it's all visible on one screen. You're more likely to get a good answer if you make it easy for us to understand what you're actually asking.
– glennsl
Nov 21 '18 at 18:33
add a comment |
6
Could you explain what your code is doing, what specific problem you're struggling with and preferably also format your code so it's all visible on one screen. You're more likely to get a good answer if you make it easy for us to understand what you're actually asking.
– glennsl
Nov 21 '18 at 18:33
6
6
Could you explain what your code is doing, what specific problem you're struggling with and preferably also format your code so it's all visible on one screen. You're more likely to get a good answer if you make it easy for us to understand what you're actually asking.
– glennsl
Nov 21 '18 at 18:33
Could you explain what your code is doing, what specific problem you're struggling with and preferably also format your code so it's all visible on one screen. You're more likely to get a good answer if you make it easy for us to understand what you're actually asking.
– glennsl
Nov 21 '18 at 18:33
add a comment |
1 Answer
1
active
oldest
votes
To build a list using fold it is probably easier to use fold_right, because you can only prepend elements to a list efficiently, and thus you should start building the list from the right, which is what fold_right does. (You can also use fold_left but then you need to reverse the list in an additional step or use the expensive list concatenation.)
A more simple example for building a list with fold_right would be to build a list of sums of elements of a list starting at the end of the list, e.g., sums [a; b; c] gives [a+b+c; b+c; c]. The code looks as follows.
let sums = List.fold_right
(fun x ys ->
match ys with
| -> [x]
| hd :: tl -> (x + hd) :: ys)
[1; 2; 3; 4; 5]
What the inner function does is to take the first element of the already built list and add it to the current element. (Keep in mind that the elements are visited from right to left.) Then the sum is added to the front of the already existing list.
Defining the non_decresing function works in a similar way. We have to work, however, with nested lists, which makes things a bit more complicated. The code is as follows.
let non_decreasing xs =
List.fold_right
(fun x outer ->
match outer with
| -> [[x]]
| outer_hd :: outer_tl ->
if x <= List.hd outer_hd then
(x :: outer_hd) :: outer_tl
else
[x] :: outer)
xs
Again, we are building the list from right to left, but this time we have to decide to which of the two lists, we add the new element. Either we add it to the head of the outer list or we add a new list, containing just the current element, to the beginning of the outer list.
answered Nov 29 '18 at 16:44
H. RittichH. Rittich
23219
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%2f53418153%2fhow-can-i-make-non-decreasing-list-of-lists-from-one-list-without-using-recursi%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
To build a list using fold it is probably easier to use fold_right, because you can only prepend elements to a list efficiently, and thus you should start building the list from the right, which is what fold_right does. (You can also use fold_left but then you need to reverse the list in an additional step or use the expensive list concatenation.)
A more simple example for building a list with fold_right would be to build a list of sums of elements of a list starting at the end of the list, e.g., sums [a; b; c] gives [a+b+c; b+c; c]. The code looks as follows.
let sums = List.fold_right
(fun x ys ->
match ys with
| -> [x]
| hd :: tl -> (x + hd) :: ys)
[1; 2; 3; 4; 5]
What the inner function does is to take the first element of the already built list and add it to the current element. (Keep in mind that the elements are visited from right to left.) Then the sum is added to the front of the already existing list.
Defining the non_decresing function works in a similar way. We have to work, however, with nested lists, which makes things a bit more complicated. The code is as follows.
let non_decreasing xs =
List.fold_right
(fun x outer ->
match outer with
| -> [[x]]
| outer_hd :: outer_tl ->
if x <= List.hd outer_hd then
(x :: outer_hd) :: outer_tl
else
[x] :: outer)
xs
Again, we are building the list from right to left, but this time we have to decide to which of the two lists, we add the new element. Either we add it to the head of the outer list or we add a new list, containing just the current element, to the beginning of the outer list.
answered Nov 29 '18 at 16:44
H. RittichH. Rittich
23219
add a comment |
To build a list using fold it is probably easier to use fold_right, because you can only prepend elements to a list efficiently, and thus you should start building the list from the right, which is what fold_right does. (You can also use fold_left but then you need to reverse the list in an additional step or use the expensive list concatenation.)
A more simple example for building a list with fold_right would be to build a list of sums of elements of a list starting at the end of the list, e.g., sums [a; b; c] gives [a+b+c; b+c; c]. The code looks as follows.
let sums = List.fold_right
(fun x ys ->
match ys with
| -> [x]
| hd :: tl -> (x + hd) :: ys)
[1; 2; 3; 4; 5]
What the inner function does is to take the first element of the already built list and add it to the current element. (Keep in mind that the elements are visited from right to left.) Then the sum is added to the front of the already existing list.
Defining the non_decresing function works in a similar way. We have to work, however, with nested lists, which makes things a bit more complicated. The code is as follows.
let non_decreasing xs =
List.fold_right
(fun x outer ->
match outer with
| -> [[x]]
| outer_hd :: outer_tl ->
if x <= List.hd outer_hd then
(x :: outer_hd) :: outer_tl
else
[x] :: outer)
xs
Again, we are building the list from right to left, but this time we have to decide to which of the two lists, we add the new element. Either we add it to the head of the outer list or we add a new list, containing just the current element, to the beginning of the outer list.
answered Nov 29 '18 at 16:44
H. RittichH. Rittich
23219
add a comment |
To build a list using fold it is probably easier to use fold_right, because you can only prepend elements to a list efficiently, and thus you should start building the list from the right, which is what fold_right does. (You can also use fold_left but then you need to reverse the list in an additional step or use the expensive list concatenation.)
A more simple example for building a list with fold_right would be to build a list of sums of elements of a list starting at the end of the list, e.g., sums [a; b; c] gives [a+b+c; b+c; c]. The code looks as follows.
let sums = List.fold_right
(fun x ys ->
match ys with
| -> [x]
| hd :: tl -> (x + hd) :: ys)
[1; 2; 3; 4; 5]
What the inner function does is to take the first element of the already built list and add it to the current element. (Keep in mind that the elements are visited from right to left.) Then the sum is added to the front of the already existing list.
Defining the non_decresing function works in a similar way. We have to work, however, with nested lists, which makes things a bit more complicated. The code is as follows.
let non_decreasing xs =
List.fold_right
(fun x outer ->
match outer with
| -> [[x]]
| outer_hd :: outer_tl ->
if x <= List.hd outer_hd then
(x :: outer_hd) :: outer_tl
else
[x] :: outer)
xs
Again, we are building the list from right to left, but this time we have to decide to which of the two lists, we add the new element. Either we add it to the head of the outer list or we add a new list, containing just the current element, to the beginning of the outer list.
answered Nov 29 '18 at 16:44
H. RittichH. Rittich
23219
To build a list using fold it is probably easier to use fold_right, because you can only prepend elements to a list efficiently, and thus you should start building the list from the right, which is what fold_right does. (You can also use fold_left but then you need to reverse the list in an additional step or use the expensive list concatenation.)
A more simple example for building a list with fold_right would be to build a list of sums of elements of a list starting at the end of the list, e.g., sums [a; b; c] gives [a+b+c; b+c; c]. The code looks as follows.
let sums = List.fold_right
(fun x ys ->
match ys with
| -> [x]
| hd :: tl -> (x + hd) :: ys)
[1; 2; 3; 4; 5]
What the inner function does is to take the first element of the already built list and add it to the current element. (Keep in mind that the elements are visited from right to left.) Then the sum is added to the front of the already existing list.
Defining the non_decresing function works in a similar way. We have to work, however, with nested lists, which makes things a bit more complicated. The code is as follows.
let non_decreasing xs =
List.fold_right
(fun x outer ->
match outer with
| -> [[x]]
| outer_hd :: outer_tl ->
if x <= List.hd outer_hd then
(x :: outer_hd) :: outer_tl
else
[x] :: outer)
xs
Again, we are building the list from right to left, but this time we have to decide to which of the two lists, we add the new element. Either we add it to the head of the outer list or we add a new list, containing just the current element, to the beginning of the outer list.
answered Nov 29 '18 at 16:44
H. RittichH. Rittich
23219
answered Nov 29 '18 at 16:44
H. RittichH. Rittich
23219
answered Nov 29 '18 at 16:44
H. RittichH. Rittich
23219
answered Nov 29 '18 at 16:44
H. RittichH. Rittich
23219
23219
add a comment |
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%2f53418153%2fhow-can-i-make-non-decreasing-list-of-lists-from-one-list-without-using-recursi%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
6
Could you explain what your code is doing, what specific problem you're struggling with and preferably also format your code so it's all visible on one screen. You're more likely to get a good answer if you make it easy for us to understand what you're actually asking.
– glennsl
Nov 21 '18 at 18:33