#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2011
    Posts
    43
    Rep Power
    4

    Partial sum in Standard ML?


    Im new to functional programming and I have an assignment to compute partial sum of a list.
    E.g. - psum [1,1,1,1,1]; val it = [1,2,3,4,5] : int list

    Here is the my code so far. However my function just returns the list as it is.

    Code:
     fun psum([])=[]
    | ppsum2(x::L) = x::ppsum2(L);
    
    psum([2,3,4]);
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    I'm not familiar with Standard ML, but your function does not appear to do any addition so it seems quite likely that it won't give a sum.

    It may help you to think about the smallest inputs and outputs and then generalize:
    Code:
    [] => []
    [x] => [x]
    [x,y] => [x, x + y]
    [x,y,z] => [x, x + y, x + y + z]
    Two things that stand out to me are

    The Nth element of the result is the (N-1)th element of the result plus the Nth element of the input.

    Every element of the result starting from the (N+1)th contains an (a+...) term where a is the Nth value in the input.

    The final element in the result is the sum of the list; The remaining elements of the result is the result of the function applied to all but the final element.

    Expressing any of those ideas in code will yield the solution.


    The Haskell function scanl performs a similar function to what you're describing. Haskell has a similar syntax to Standard ML. Maybe it would help to examine its source: GHC's source for scanl

    Code:
    F:\>ghci
    GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
    Prelude> scanl (+) 0 [1,1,1,1,1]
    [0,1,2,3,4,5]
    Prelude> scanl (+) 0 [2,3,4]
    [0,2,5,9]

    It also might help to get into the mind set of list manipulations by implementing some of the simpler functions like "map transform list" (apply 'transform' to each element of 'list') and "fold reduction initial list" (apply 'reduction' to 'initial' and the first element of 'list', then apply 'reduction' to the result and the next element of 'list', continue until list is consumed).

    Comments on this post

    • sepp2k1 agrees
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    1
    Rep Power
    0
    Originally Posted by lisa92
    Im new to functional programming and I have an assignment to compute partial sum of a list.
    E.g. - psum [1,1,1,1,1]; val it = [1,2,3,4,5] : int list

    Here is the my code so far. However my function just returns the list as it is.

    Code:
     fun psum([])=[]
    | ppsum2(x::L) = x::ppsum2(L);
    
    psum([2,3,4]);
    fun psum [] ys = List.rev ys
    | psum (x::xs) [] = psum xs [x]
    | psum (x::xs) (y::ys) = psum xs ((x + y)::y::ys)

    val a = psum [1,1,1,1,1] []
    [CODE]

    That should do the trick.

IMN logo majestic logo threadwatch logo seochat tools logo