sml - Counting how many elements in a sorted list, that are larger than a given predicate -
i'm trying create function finds how many elements bigger first element divided 2 in given sorted list. example given list [3,3,4,5,6,7,8,9,11], first element 3, numbers larger divided 2 7,8,9,11 function returns 4.
i have done far doesn't work. a element first of list , given in order easier.
fun findlarger [] = | findlarger [] = 0 | findlarger [x] = 0 | findlarger (x::xs) = let val = ref a; in if !a < x/2 length (xs) + 1 else findlarger (a, xs) end
i don't know start pointing out issues code. seems have misunderstood basics of functional programming.
- first off should not using references (unless know doing, @ still wrong), should use recursion.
- you haven't declared function take same number of arguments. in first clause, have defined 2 curried arguments, in rest of clauses have 1 argument, , in second last line of code, calling function pair argument.
- your first function clause don't have body.
"<"not strictly less operator in sml. have written there, string.
fixing original code result in this. note first element put list, such know compare with.
fun findlarger [] = 0 | findlarger [x] = 0 | findlarger (x::y::xs) = if y > x*2 1 + findlarger(x :: xs) else findlarger(x :: xs) however have made internal helper function , done calculation of x*2, won't calculated every time
fun findlarger [] = 0 | findlarger (x::xs) = let val xx = 2*x fun f [] = 0 | f (y::ys) = (if y > xx 1 else 0) + f ys in f xs end if using higher order functions suggested in other answer, should avoid traversing list twice (first filtering out elements , counting remaining). should go through list once, , count elements match given predicate.
accomplish functionality, may use 1 of fold functions. in cases makes sense use foldl, traverse list left right in tail recursive manner.
fun p (x, y) = if y > 2*x 1 else 0 fun f [] = 0 | f (x::xs) = foldl (fn (a,b) => b + p(x, a)) 0 xs 