listelm

Position of element in List


I'm trying to get the index of an element in a list given its Id. This is what I have:

type alias Id = Int  

posInList : Id -> List (Id, ItemModel) -> Int
posInList id list =
  if List.isEmpty list then 
      -1
  else 
    if (List.head list).fst == id then
      0
    else 
      if posInList id (List.tail list) == -1 then
        -1
      else
        posInList id (List.tail list) + 1

I got that from scheme-code found here (answer with 7 votes).

When I compile the code I get two errors:

type-mismatch enter image description here

How do I solve this? Or is there a simpler solution?

Update: tried it with Maybe

posInList : Id -> Maybe List (Id, ItemModel) -> Int
posInList id list =
  case list of
    Nothing -> -1
    Just a -> 
      case (List.head a) of
        Just b -> 
          if b.fst == id then 
            0
          else
            case (List.tail a) of
              Nothing -> -1
              Just c -> (posInList id (Just c)) + 1
        Nothing -> -1

I think I'm close but I can't resolve this error:

just-c

Just c is of type Maybe List but where does that conflict with Maybe? I thought the type annotation so I added brackets like so:

posInList : Id -> Maybe (List (Id, ItemModel)) -> Int

But then I get:

enter image description here

And now I'm clueless, never seen an error like that.


Solution

  • First it may help to break it down into a simpler indexOf function to avoid having to deal with the specific tuple model you're using. This makes it a little cleaner and more reusable.

    We'll define indexOf as this:

    indexOf : a -> List a -> Maybe Int
    indexOf el list =
      let
        indexOf' list' index =
          case list' of
            [] ->
              Nothing
            (x::xs) ->
              if x == el then
                Just index
              else
                indexOf' xs (index + 1)
      in
        indexOf' list 0
    

    There's nothing special going on here, it's just pattern matching and a recursive call. The sub-function, indexOf' is used to keep track of the current index.

    Now we have a general purpose indexOf function that can be used on any comparable type, not just integers.

    Next we need to squeeze in your list of type List (Id, ItemModel). This is where we can use fst in the map function, creating a list of Ids.

    posInList : Id -> List (Id, ItemModel) -> Int
    posInList id list =
      case indexOf id (List.map fst list) of
        Nothing ->
          -1
        Just index ->
           index
    

    Your original implementation was returning -1 in the case when something is not found, but I think it would be more idiomatic to return a Maybe Int instead. That would make it clear what your intention was to anyone else using the library.