Wayne Shorter was one of the finest of the hardbop composers. I think he produced more haunting melodies than anyone else I know of. Indeed many of his works are literally haunting, with titles like 'Infant Eyes,' and 'Juju.'
'Footprints' might be his most covered composition. I am pretty sure it shows up first on Adam's Apple, a 1966 Shorter album with Herbie Hancock, Reggie Workman, and Joe Chambers. I happen to think that 'Adam's Apple' is as good a song, but who's counting? Shorter recorded 'Footprints' with Miles Davis on Miles Smiles that same year.
Footprints is surely an immortal piece of music. Go back to the November Jazznotes, and you can hear a recording of of the song by Chico Freeman and Arthur Blythe. But here is something different: a version with words by Karrin Allyson.
ps. I just listened to both Allyson's version and the Freeman/Blythe. Boy are they both toe-curlin' good. The difference between the two is a brilliant illustration of how much life there is in one good melody, and that is the story of modern jazz. If you like what you hear, get the whole albums. Both are available for a song at eMusic.