How to combine equal sequence elements (functional programming)?











up vote
1
down vote

favorite












I want to write a function that takes in a sequence <1,1,2,2,3> and returns the sequence with equal elements grouped like <<1,1>, <2,2>, <3>>.



I'm using sequences, not lists, but some of the functions are similar. Some of the functions I am thinking of using are map, reduce, tabulate, filter, append etc..



Reduce takes in an associative function and returns the sequence that is "reduced" by that operator. So, reduce op+ 0 <1,2,3> = 6.



My first thought was to use map to raise the sequence by one level.
So, <1,1,2,2,3> => <<1>,<1>,<2>,<2>,<3>>.



Then, I was thinking of using reduce, in which I create a function that takes pairs of elements like (x,y). If x == y, then I return else, I do nothing. But...this doesn't exactly work since the function has to return something of the same type in both cases.



Can someone give me some tips on the right path to take, like what higher order functions I could possibly use? I'm using SML but I'm not asking for anyone to give me a full blown answer so any high-level tips would be appreciated (in any functional language honestly)










share|improve this question






















  • Don't know about the languages you are using, but from functional perspective, I would: 1) take sequence of distinct values 2) map each value in distinct sequence to filtered original sequence.
    – muradm
    Nov 10 at 23:22















up vote
1
down vote

favorite












I want to write a function that takes in a sequence <1,1,2,2,3> and returns the sequence with equal elements grouped like <<1,1>, <2,2>, <3>>.



I'm using sequences, not lists, but some of the functions are similar. Some of the functions I am thinking of using are map, reduce, tabulate, filter, append etc..



Reduce takes in an associative function and returns the sequence that is "reduced" by that operator. So, reduce op+ 0 <1,2,3> = 6.



My first thought was to use map to raise the sequence by one level.
So, <1,1,2,2,3> => <<1>,<1>,<2>,<2>,<3>>.



Then, I was thinking of using reduce, in which I create a function that takes pairs of elements like (x,y). If x == y, then I return else, I do nothing. But...this doesn't exactly work since the function has to return something of the same type in both cases.



Can someone give me some tips on the right path to take, like what higher order functions I could possibly use? I'm using SML but I'm not asking for anyone to give me a full blown answer so any high-level tips would be appreciated (in any functional language honestly)










share|improve this question






















  • Don't know about the languages you are using, but from functional perspective, I would: 1) take sequence of distinct values 2) map each value in distinct sequence to filtered original sequence.
    – muradm
    Nov 10 at 23:22













up vote
1
down vote

favorite









up vote
1
down vote

favorite











I want to write a function that takes in a sequence <1,1,2,2,3> and returns the sequence with equal elements grouped like <<1,1>, <2,2>, <3>>.



I'm using sequences, not lists, but some of the functions are similar. Some of the functions I am thinking of using are map, reduce, tabulate, filter, append etc..



Reduce takes in an associative function and returns the sequence that is "reduced" by that operator. So, reduce op+ 0 <1,2,3> = 6.



My first thought was to use map to raise the sequence by one level.
So, <1,1,2,2,3> => <<1>,<1>,<2>,<2>,<3>>.



Then, I was thinking of using reduce, in which I create a function that takes pairs of elements like (x,y). If x == y, then I return else, I do nothing. But...this doesn't exactly work since the function has to return something of the same type in both cases.



Can someone give me some tips on the right path to take, like what higher order functions I could possibly use? I'm using SML but I'm not asking for anyone to give me a full blown answer so any high-level tips would be appreciated (in any functional language honestly)










share|improve this question













I want to write a function that takes in a sequence <1,1,2,2,3> and returns the sequence with equal elements grouped like <<1,1>, <2,2>, <3>>.



I'm using sequences, not lists, but some of the functions are similar. Some of the functions I am thinking of using are map, reduce, tabulate, filter, append etc..



Reduce takes in an associative function and returns the sequence that is "reduced" by that operator. So, reduce op+ 0 <1,2,3> = 6.



My first thought was to use map to raise the sequence by one level.
So, <1,1,2,2,3> => <<1>,<1>,<2>,<2>,<3>>.



Then, I was thinking of using reduce, in which I create a function that takes pairs of elements like (x,y). If x == y, then I return else, I do nothing. But...this doesn't exactly work since the function has to return something of the same type in both cases.



Can someone give me some tips on the right path to take, like what higher order functions I could possibly use? I'm using SML but I'm not asking for anyone to give me a full blown answer so any high-level tips would be appreciated (in any functional language honestly)







functional-programming f# ocaml sml






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Nov 10 at 22:58









tsent2

61




61












  • Don't know about the languages you are using, but from functional perspective, I would: 1) take sequence of distinct values 2) map each value in distinct sequence to filtered original sequence.
    – muradm
    Nov 10 at 23:22


















  • Don't know about the languages you are using, but from functional perspective, I would: 1) take sequence of distinct values 2) map each value in distinct sequence to filtered original sequence.
    – muradm
    Nov 10 at 23:22
















Don't know about the languages you are using, but from functional perspective, I would: 1) take sequence of distinct values 2) map each value in distinct sequence to filtered original sequence.
– muradm
Nov 10 at 23:22




Don't know about the languages you are using, but from functional perspective, I would: 1) take sequence of distinct values 2) map each value in distinct sequence to filtered original sequence.
– muradm
Nov 10 at 23:22












4 Answers
4






active

oldest

votes

















up vote
3
down vote













I guess that the reduce function you are referring to is the same as the fold function in F#:



val fold : ('State -> 'Value -> 'State) -> 'State -> 'Value list -> 'State


This takes a list of values, together with an initial state and a function that transforms the state while iterating through the values of the list.



You can do what you want in a single fold. There are a couple of things that you'll need to keep in the state. Imagine you are somewhere in the middle of 1,1,2,2,3 (say, on the second 2). Now you'll need:




  • The value that you are currently collecting - that is 2

  • A list of values containing the currently collected values - that is [2] (the first 2 from the sequence)

  • A list of lists of values you collected previously - that is [ [1; 1] ].


You would start with an initial state -1, , (using -1 as some value that won't appear in your input). Then you need to write the function that transforms the state based on a current value. This needs to handle a couple of situations:




  • When the value is not the same as the values you've been collecting, you need to add the list of collected values to the list of lists (unless it is empty)

  • When the value is the same, you need to add it to the list of values collected now and continue


Hopefully, this gives you enough information to figure out how to do this, without actually revealing the full source code!






share|improve this answer




























    up vote
    2
    down vote













    If F# is your language, simply use the Seq.groupBy function:



    input |> Seq.groupBy id |> Seq.map snd


    Otherwise,



    I assume that your language supports Seq.distinct, Seq.fold, Seq.map, and Seq.init. The F# version of these functions can be found in this document.



    Then you can do the steps below:



    1) Make a distinct seq of the input seq with Seq.distinct:



    input |> Seq.distinct


    2) Write a function that counts the number of occurrences of a value in a seq by using Seq.fold:



    let count x theSeq =
    theSeq
    |> Seq.fold (fun n e -> if x = e then n+1 else n) 0


    3) Use the count function to decorate each element of the distinct seq with the number of its occurrences in the input seq:



    Seq.map (fun x -> (x, count x input))


    4) Finally, use Seq.init to replicate the equal elements:



    Seq.map (fun (x, count) -> Seq.init count (fun i -> x))


    The whole code:



    let count x theSeq =
    theSeq
    |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

    input
    |> Seq.distinct
    |> Seq.map (fun x -> (x, count x input))
    |> Seq.map (fun (x, count) -> Seq.init count (fun i -> x))





    share|improve this answer






























      up vote
      0
      down vote













      Don't know about the languages you are using, but from functional perspective, I would:




      1. take sequence of distinct values

      2. map each value in distinct sequence to filtered original sequence.


      Pseudo code:



      originalSequence = <1,1,2,2,3>
      distinctSequence = originalSequnce.distinct() // <1,2,3>
      result = distinctSequence.map(elem => originalSequence.filter(e == elem)) // <<1,1>, <2, 2>, <3>>





      share|improve this answer




























        up vote
        0
        down vote













        In Haskell you have group and groupBy. They're made with a helper function called span. Standard ML unfortunately does not have as rich a standard library, so you'll have to create the function yourself. But you could use the same approach:





        1. Define a function span that splits a list in two where the first part is the longest prefix for which some predicate is true, and the second part is the remainder of the list.



          fun span p  = ...
          | span p (x::xs) = ... if p x then ... else ...


          For example,



          - span (fn n => n <= 3) [2,3,4,1,5]
          > val it = ([2,3], [4,1,5])


          This is a little difficult because you must somehow add x to the result of calling span p xs recursively, even though it returns a pair of lists; so you cannot just write x :: span p xs; you have to unpack the pair that is returned and return (x :: ys, zs) or (ys, x :: zs) (and stop recursing once p x is false).




        2. Define a function groupBy that uses span. The function that groupBy uses should have two arguments unlike in span where p took one argument: The first one is the element with which to group, and the second is the subsequent elements.



          fun groupBy f  = ...
          | groupBy f (x::xs) = ... use span, f, x and xs to create (ys, zs) ...
          ... ys is the first group ...
          ... groupBy f zs is the remaining groups ...


          Here it helps if the function f is curried, i.e. has type



          'a -> 'a -> bool


          since then it can be used like val (ys, zs) = span (f x) xs.




        Feel free to ask follow-up questions if you want to use this approach.






        share|improve this answer





















          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',
          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%2f53244247%2fhow-to-combine-equal-sequence-elements-functional-programming%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          4 Answers
          4






          active

          oldest

          votes








          4 Answers
          4






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          3
          down vote













          I guess that the reduce function you are referring to is the same as the fold function in F#:



          val fold : ('State -> 'Value -> 'State) -> 'State -> 'Value list -> 'State


          This takes a list of values, together with an initial state and a function that transforms the state while iterating through the values of the list.



          You can do what you want in a single fold. There are a couple of things that you'll need to keep in the state. Imagine you are somewhere in the middle of 1,1,2,2,3 (say, on the second 2). Now you'll need:




          • The value that you are currently collecting - that is 2

          • A list of values containing the currently collected values - that is [2] (the first 2 from the sequence)

          • A list of lists of values you collected previously - that is [ [1; 1] ].


          You would start with an initial state -1, , (using -1 as some value that won't appear in your input). Then you need to write the function that transforms the state based on a current value. This needs to handle a couple of situations:




          • When the value is not the same as the values you've been collecting, you need to add the list of collected values to the list of lists (unless it is empty)

          • When the value is the same, you need to add it to the list of values collected now and continue


          Hopefully, this gives you enough information to figure out how to do this, without actually revealing the full source code!






          share|improve this answer

























            up vote
            3
            down vote













            I guess that the reduce function you are referring to is the same as the fold function in F#:



            val fold : ('State -> 'Value -> 'State) -> 'State -> 'Value list -> 'State


            This takes a list of values, together with an initial state and a function that transforms the state while iterating through the values of the list.



            You can do what you want in a single fold. There are a couple of things that you'll need to keep in the state. Imagine you are somewhere in the middle of 1,1,2,2,3 (say, on the second 2). Now you'll need:




            • The value that you are currently collecting - that is 2

            • A list of values containing the currently collected values - that is [2] (the first 2 from the sequence)

            • A list of lists of values you collected previously - that is [ [1; 1] ].


            You would start with an initial state -1, , (using -1 as some value that won't appear in your input). Then you need to write the function that transforms the state based on a current value. This needs to handle a couple of situations:




            • When the value is not the same as the values you've been collecting, you need to add the list of collected values to the list of lists (unless it is empty)

            • When the value is the same, you need to add it to the list of values collected now and continue


            Hopefully, this gives you enough information to figure out how to do this, without actually revealing the full source code!






            share|improve this answer























              up vote
              3
              down vote










              up vote
              3
              down vote









              I guess that the reduce function you are referring to is the same as the fold function in F#:



              val fold : ('State -> 'Value -> 'State) -> 'State -> 'Value list -> 'State


              This takes a list of values, together with an initial state and a function that transforms the state while iterating through the values of the list.



              You can do what you want in a single fold. There are a couple of things that you'll need to keep in the state. Imagine you are somewhere in the middle of 1,1,2,2,3 (say, on the second 2). Now you'll need:




              • The value that you are currently collecting - that is 2

              • A list of values containing the currently collected values - that is [2] (the first 2 from the sequence)

              • A list of lists of values you collected previously - that is [ [1; 1] ].


              You would start with an initial state -1, , (using -1 as some value that won't appear in your input). Then you need to write the function that transforms the state based on a current value. This needs to handle a couple of situations:




              • When the value is not the same as the values you've been collecting, you need to add the list of collected values to the list of lists (unless it is empty)

              • When the value is the same, you need to add it to the list of values collected now and continue


              Hopefully, this gives you enough information to figure out how to do this, without actually revealing the full source code!






              share|improve this answer












              I guess that the reduce function you are referring to is the same as the fold function in F#:



              val fold : ('State -> 'Value -> 'State) -> 'State -> 'Value list -> 'State


              This takes a list of values, together with an initial state and a function that transforms the state while iterating through the values of the list.



              You can do what you want in a single fold. There are a couple of things that you'll need to keep in the state. Imagine you are somewhere in the middle of 1,1,2,2,3 (say, on the second 2). Now you'll need:




              • The value that you are currently collecting - that is 2

              • A list of values containing the currently collected values - that is [2] (the first 2 from the sequence)

              • A list of lists of values you collected previously - that is [ [1; 1] ].


              You would start with an initial state -1, , (using -1 as some value that won't appear in your input). Then you need to write the function that transforms the state based on a current value. This needs to handle a couple of situations:




              • When the value is not the same as the values you've been collecting, you need to add the list of collected values to the list of lists (unless it is empty)

              • When the value is the same, you need to add it to the list of values collected now and continue


              Hopefully, this gives you enough information to figure out how to do this, without actually revealing the full source code!







              share|improve this answer












              share|improve this answer



              share|improve this answer










              answered Nov 10 at 23:33









              Tomas Petricek

              196k13285458




              196k13285458
























                  up vote
                  2
                  down vote













                  If F# is your language, simply use the Seq.groupBy function:



                  input |> Seq.groupBy id |> Seq.map snd


                  Otherwise,



                  I assume that your language supports Seq.distinct, Seq.fold, Seq.map, and Seq.init. The F# version of these functions can be found in this document.



                  Then you can do the steps below:



                  1) Make a distinct seq of the input seq with Seq.distinct:



                  input |> Seq.distinct


                  2) Write a function that counts the number of occurrences of a value in a seq by using Seq.fold:



                  let count x theSeq =
                  theSeq
                  |> Seq.fold (fun n e -> if x = e then n+1 else n) 0


                  3) Use the count function to decorate each element of the distinct seq with the number of its occurrences in the input seq:



                  Seq.map (fun x -> (x, count x input))


                  4) Finally, use Seq.init to replicate the equal elements:



                  Seq.map (fun (x, count) -> Seq.init count (fun i -> x))


                  The whole code:



                  let count x theSeq =
                  theSeq
                  |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

                  input
                  |> Seq.distinct
                  |> Seq.map (fun x -> (x, count x input))
                  |> Seq.map (fun (x, count) -> Seq.init count (fun i -> x))





                  share|improve this answer



























                    up vote
                    2
                    down vote













                    If F# is your language, simply use the Seq.groupBy function:



                    input |> Seq.groupBy id |> Seq.map snd


                    Otherwise,



                    I assume that your language supports Seq.distinct, Seq.fold, Seq.map, and Seq.init. The F# version of these functions can be found in this document.



                    Then you can do the steps below:



                    1) Make a distinct seq of the input seq with Seq.distinct:



                    input |> Seq.distinct


                    2) Write a function that counts the number of occurrences of a value in a seq by using Seq.fold:



                    let count x theSeq =
                    theSeq
                    |> Seq.fold (fun n e -> if x = e then n+1 else n) 0


                    3) Use the count function to decorate each element of the distinct seq with the number of its occurrences in the input seq:



                    Seq.map (fun x -> (x, count x input))


                    4) Finally, use Seq.init to replicate the equal elements:



                    Seq.map (fun (x, count) -> Seq.init count (fun i -> x))


                    The whole code:



                    let count x theSeq =
                    theSeq
                    |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

                    input
                    |> Seq.distinct
                    |> Seq.map (fun x -> (x, count x input))
                    |> Seq.map (fun (x, count) -> Seq.init count (fun i -> x))





                    share|improve this answer

























                      up vote
                      2
                      down vote










                      up vote
                      2
                      down vote









                      If F# is your language, simply use the Seq.groupBy function:



                      input |> Seq.groupBy id |> Seq.map snd


                      Otherwise,



                      I assume that your language supports Seq.distinct, Seq.fold, Seq.map, and Seq.init. The F# version of these functions can be found in this document.



                      Then you can do the steps below:



                      1) Make a distinct seq of the input seq with Seq.distinct:



                      input |> Seq.distinct


                      2) Write a function that counts the number of occurrences of a value in a seq by using Seq.fold:



                      let count x theSeq =
                      theSeq
                      |> Seq.fold (fun n e -> if x = e then n+1 else n) 0


                      3) Use the count function to decorate each element of the distinct seq with the number of its occurrences in the input seq:



                      Seq.map (fun x -> (x, count x input))


                      4) Finally, use Seq.init to replicate the equal elements:



                      Seq.map (fun (x, count) -> Seq.init count (fun i -> x))


                      The whole code:



                      let count x theSeq =
                      theSeq
                      |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

                      input
                      |> Seq.distinct
                      |> Seq.map (fun x -> (x, count x input))
                      |> Seq.map (fun (x, count) -> Seq.init count (fun i -> x))





                      share|improve this answer














                      If F# is your language, simply use the Seq.groupBy function:



                      input |> Seq.groupBy id |> Seq.map snd


                      Otherwise,



                      I assume that your language supports Seq.distinct, Seq.fold, Seq.map, and Seq.init. The F# version of these functions can be found in this document.



                      Then you can do the steps below:



                      1) Make a distinct seq of the input seq with Seq.distinct:



                      input |> Seq.distinct


                      2) Write a function that counts the number of occurrences of a value in a seq by using Seq.fold:



                      let count x theSeq =
                      theSeq
                      |> Seq.fold (fun n e -> if x = e then n+1 else n) 0


                      3) Use the count function to decorate each element of the distinct seq with the number of its occurrences in the input seq:



                      Seq.map (fun x -> (x, count x input))


                      4) Finally, use Seq.init to replicate the equal elements:



                      Seq.map (fun (x, count) -> Seq.init count (fun i -> x))


                      The whole code:



                      let count x theSeq =
                      theSeq
                      |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

                      input
                      |> Seq.distinct
                      |> Seq.map (fun x -> (x, count x input))
                      |> Seq.map (fun (x, count) -> Seq.init count (fun i -> x))






                      share|improve this answer














                      share|improve this answer



                      share|improve this answer








                      edited Nov 11 at 15:30

























                      answered Nov 11 at 4:25









                      Nghia Bui

                      1,443812




                      1,443812






















                          up vote
                          0
                          down vote













                          Don't know about the languages you are using, but from functional perspective, I would:




                          1. take sequence of distinct values

                          2. map each value in distinct sequence to filtered original sequence.


                          Pseudo code:



                          originalSequence = <1,1,2,2,3>
                          distinctSequence = originalSequnce.distinct() // <1,2,3>
                          result = distinctSequence.map(elem => originalSequence.filter(e == elem)) // <<1,1>, <2, 2>, <3>>





                          share|improve this answer

























                            up vote
                            0
                            down vote













                            Don't know about the languages you are using, but from functional perspective, I would:




                            1. take sequence of distinct values

                            2. map each value in distinct sequence to filtered original sequence.


                            Pseudo code:



                            originalSequence = <1,1,2,2,3>
                            distinctSequence = originalSequnce.distinct() // <1,2,3>
                            result = distinctSequence.map(elem => originalSequence.filter(e == elem)) // <<1,1>, <2, 2>, <3>>





                            share|improve this answer























                              up vote
                              0
                              down vote










                              up vote
                              0
                              down vote









                              Don't know about the languages you are using, but from functional perspective, I would:




                              1. take sequence of distinct values

                              2. map each value in distinct sequence to filtered original sequence.


                              Pseudo code:



                              originalSequence = <1,1,2,2,3>
                              distinctSequence = originalSequnce.distinct() // <1,2,3>
                              result = distinctSequence.map(elem => originalSequence.filter(e == elem)) // <<1,1>, <2, 2>, <3>>





                              share|improve this answer












                              Don't know about the languages you are using, but from functional perspective, I would:




                              1. take sequence of distinct values

                              2. map each value in distinct sequence to filtered original sequence.


                              Pseudo code:



                              originalSequence = <1,1,2,2,3>
                              distinctSequence = originalSequnce.distinct() // <1,2,3>
                              result = distinctSequence.map(elem => originalSequence.filter(e == elem)) // <<1,1>, <2, 2>, <3>>






                              share|improve this answer












                              share|improve this answer



                              share|improve this answer










                              answered Nov 10 at 23:26









                              muradm

                              732419




                              732419






















                                  up vote
                                  0
                                  down vote













                                  In Haskell you have group and groupBy. They're made with a helper function called span. Standard ML unfortunately does not have as rich a standard library, so you'll have to create the function yourself. But you could use the same approach:





                                  1. Define a function span that splits a list in two where the first part is the longest prefix for which some predicate is true, and the second part is the remainder of the list.



                                    fun span p  = ...
                                    | span p (x::xs) = ... if p x then ... else ...


                                    For example,



                                    - span (fn n => n <= 3) [2,3,4,1,5]
                                    > val it = ([2,3], [4,1,5])


                                    This is a little difficult because you must somehow add x to the result of calling span p xs recursively, even though it returns a pair of lists; so you cannot just write x :: span p xs; you have to unpack the pair that is returned and return (x :: ys, zs) or (ys, x :: zs) (and stop recursing once p x is false).




                                  2. Define a function groupBy that uses span. The function that groupBy uses should have two arguments unlike in span where p took one argument: The first one is the element with which to group, and the second is the subsequent elements.



                                    fun groupBy f  = ...
                                    | groupBy f (x::xs) = ... use span, f, x and xs to create (ys, zs) ...
                                    ... ys is the first group ...
                                    ... groupBy f zs is the remaining groups ...


                                    Here it helps if the function f is curried, i.e. has type



                                    'a -> 'a -> bool


                                    since then it can be used like val (ys, zs) = span (f x) xs.




                                  Feel free to ask follow-up questions if you want to use this approach.






                                  share|improve this answer

























                                    up vote
                                    0
                                    down vote













                                    In Haskell you have group and groupBy. They're made with a helper function called span. Standard ML unfortunately does not have as rich a standard library, so you'll have to create the function yourself. But you could use the same approach:





                                    1. Define a function span that splits a list in two where the first part is the longest prefix for which some predicate is true, and the second part is the remainder of the list.



                                      fun span p  = ...
                                      | span p (x::xs) = ... if p x then ... else ...


                                      For example,



                                      - span (fn n => n <= 3) [2,3,4,1,5]
                                      > val it = ([2,3], [4,1,5])


                                      This is a little difficult because you must somehow add x to the result of calling span p xs recursively, even though it returns a pair of lists; so you cannot just write x :: span p xs; you have to unpack the pair that is returned and return (x :: ys, zs) or (ys, x :: zs) (and stop recursing once p x is false).




                                    2. Define a function groupBy that uses span. The function that groupBy uses should have two arguments unlike in span where p took one argument: The first one is the element with which to group, and the second is the subsequent elements.



                                      fun groupBy f  = ...
                                      | groupBy f (x::xs) = ... use span, f, x and xs to create (ys, zs) ...
                                      ... ys is the first group ...
                                      ... groupBy f zs is the remaining groups ...


                                      Here it helps if the function f is curried, i.e. has type



                                      'a -> 'a -> bool


                                      since then it can be used like val (ys, zs) = span (f x) xs.




                                    Feel free to ask follow-up questions if you want to use this approach.






                                    share|improve this answer























                                      up vote
                                      0
                                      down vote










                                      up vote
                                      0
                                      down vote









                                      In Haskell you have group and groupBy. They're made with a helper function called span. Standard ML unfortunately does not have as rich a standard library, so you'll have to create the function yourself. But you could use the same approach:





                                      1. Define a function span that splits a list in two where the first part is the longest prefix for which some predicate is true, and the second part is the remainder of the list.



                                        fun span p  = ...
                                        | span p (x::xs) = ... if p x then ... else ...


                                        For example,



                                        - span (fn n => n <= 3) [2,3,4,1,5]
                                        > val it = ([2,3], [4,1,5])


                                        This is a little difficult because you must somehow add x to the result of calling span p xs recursively, even though it returns a pair of lists; so you cannot just write x :: span p xs; you have to unpack the pair that is returned and return (x :: ys, zs) or (ys, x :: zs) (and stop recursing once p x is false).




                                      2. Define a function groupBy that uses span. The function that groupBy uses should have two arguments unlike in span where p took one argument: The first one is the element with which to group, and the second is the subsequent elements.



                                        fun groupBy f  = ...
                                        | groupBy f (x::xs) = ... use span, f, x and xs to create (ys, zs) ...
                                        ... ys is the first group ...
                                        ... groupBy f zs is the remaining groups ...


                                        Here it helps if the function f is curried, i.e. has type



                                        'a -> 'a -> bool


                                        since then it can be used like val (ys, zs) = span (f x) xs.




                                      Feel free to ask follow-up questions if you want to use this approach.






                                      share|improve this answer












                                      In Haskell you have group and groupBy. They're made with a helper function called span. Standard ML unfortunately does not have as rich a standard library, so you'll have to create the function yourself. But you could use the same approach:





                                      1. Define a function span that splits a list in two where the first part is the longest prefix for which some predicate is true, and the second part is the remainder of the list.



                                        fun span p  = ...
                                        | span p (x::xs) = ... if p x then ... else ...


                                        For example,



                                        - span (fn n => n <= 3) [2,3,4,1,5]
                                        > val it = ([2,3], [4,1,5])


                                        This is a little difficult because you must somehow add x to the result of calling span p xs recursively, even though it returns a pair of lists; so you cannot just write x :: span p xs; you have to unpack the pair that is returned and return (x :: ys, zs) or (ys, x :: zs) (and stop recursing once p x is false).




                                      2. Define a function groupBy that uses span. The function that groupBy uses should have two arguments unlike in span where p took one argument: The first one is the element with which to group, and the second is the subsequent elements.



                                        fun groupBy f  = ...
                                        | groupBy f (x::xs) = ... use span, f, x and xs to create (ys, zs) ...
                                        ... ys is the first group ...
                                        ... groupBy f zs is the remaining groups ...


                                        Here it helps if the function f is curried, i.e. has type



                                        'a -> 'a -> bool


                                        since then it can be used like val (ys, zs) = span (f x) xs.




                                      Feel free to ask follow-up questions if you want to use this approach.







                                      share|improve this answer












                                      share|improve this answer



                                      share|improve this answer










                                      answered Nov 11 at 14:01









                                      Simon Shine

                                      9,11312746




                                      9,11312746






























                                           

                                          draft saved


                                          draft discarded



















































                                           


                                          draft saved


                                          draft discarded














                                          StackExchange.ready(
                                          function () {
                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53244247%2fhow-to-combine-equal-sequence-elements-functional-programming%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

                                          Full-time equivalent

                                          さくらももこ

                                          13 indicted, 8 arrested in Calif. drug cartel investigation