Difficulty with filtering two lists in SML

Question

I'm trying to "double" filter through two lists depending on passing a datatype test painfully without recursion using HOPs. Below is my very-ugly attempt at a solution...

datatype 'a test = Test of ('a -> bool) * string;

fun foo xs lst = 
    let 
        fun foo_bar(x, ls) =
            let                
                val tests = (List.filter (fn (Test(f, str)) => (f x)) ls)
            in
                (List.map (fn (Test(f, str)) => str) tests)
            end 
    in
        (List.map (fn x => foo_bar(x, lst)) xs)
    end;

allPass: 'a list -> 'a test list -> 'a test list;

allPass [1, 2, 40, 150] [positive, even] should return the string "pos".

Currently, my function is returning a nested list: [["pos"], ["pos even"], ["pos even"], ["pos even"]]. Is there a non-recursive way to extract just "pos" from this result or am I going about solving this problem in entirely the wrong direction?

Perhaps you could elaborate a bit on why you would expect the function to return only a single result, instead of the list of results it does now. Also you have defined a foo function, but are using a allPass function in you example case. — Jesper.Reenberg
Note that the map and fold functions are available in the top level environment, thus you don't need to write List.map. — Jesper.Reenberg

Tayacan Tayacan · Accepted Answer · 2013-02-11T19:13:47

You're going in the right direction, but you're not quite there yet. Here's what I think you want.

Take a list of value and a list of Tests. Return a list of the names of the tests for which all of the values pass.

Okay, so we need to:

Filter the list of tests. The predicate for a test is that all the values must pass.
Extract the names of the tests that passed.

Okay, so how do we figure out if all the values in a list pass one test? Simple, we use List.all.

List.all    : ('a -> bool) -> 'a list -> bool

We can define a function:

fun allPassesTest xs (Test(f,s)) = List.all f xs

This will return true if and only if all of the values in xs pass the test. Now we filter the list of tests, based on this function:

fun allPass xs tests = List.filter allPassesTest xs tests

However, this returns a 'a test list instead of a string list, so you'll need to extract the names.

fun name (Test(f,s)) = s
fun allPass xs tests = map name (List.filter allPassesTest xs tests)

Difficulty with filtering two lists in SML

1 Answers